Tricolor Triangles

题意翻译

你有一个 $n$ 个点、$m$ 条边的简单无向图，每条边有颜色编号 $c_i$，要么被染成 $1,2,3$ 中的一种颜色，要么没有被染色（$c_i=-1$）。 现在，你要对未被染色的边染色，使得对于所有三元环，环上的三条边颜色各不相同或全部相同。 需输出方案。无解输出 $-1$。

题目描述

You are given a simple undirected graph with $ n $ vertices and $ m $ edges. Edge $ i $ is colored in the color $ c_i $ , which is either $ 1 $ , $ 2 $ , or $ 3 $ , or left uncolored (in this case, $ c_i = -1 $ ). You need to color all of the uncolored edges in such a way that for any three pairwise adjacent vertices $ 1 \leq a < b < c \leq n $ , the colors of the edges $ a \leftrightarrow b $ , $ b \leftrightarrow c $ , and $ a \leftrightarrow c $ are either pairwise different, or all equal. In case no such coloring exists, you need to determine that.

输入输出格式

输入格式

The first line of input contains one integer $ t $ ( $ 1 \leq t \leq 10 $ ): the number of test cases. The following lines contain the description of the test cases. In the first line you are given two integers $ n $ and $ m $ ( $ 3 \leq n \leq 64 $ , $ 0 \leq m \leq \min(256, \frac{n(n-1)}{2}) $ ): the number of vertices and edges in the graph. Each of the next $ m $ lines contains three integers $ a_i $ , $ b_i $ , and $ c_i $ ( $ 1 \leq a_i, b_i \leq n $ , $ a_i \ne b_i $ , $ c_i $ is either $ -1 $ , $ 1 $ , $ 2 $ , or $ 3 $ ), denoting an edge between $ a_i $ and $ b_i $ with color $ c_i $ . It is guaranteed that no two edges share the same endpoints.

输出格式

For each test case, print $ m $ integers $ d_1, d_2, \ldots, d_m $ , where $ d_i $ is the color of the $ i $ -th edge in your final coloring. If there is no valid way to finish the coloring, print $ -1 $ .

输入输出样例

输入样例 #1

4
3 3
1 2 1
2 3 2
3 1 -1
3 3
1 2 1
2 3 1
3 1 -1
4 4
1 2 -1
2 3 -1
3 4 -1
4 1 -1
3 3
1 2 1
2 3 1
3 1 2

输出样例 #1

1 2 3 
1 1 1 
1 2 2 3 
-1