CF1616F.Tricolor Triangles

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 \lt b \lt 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.

给你一个包含 $n$ 个顶点和 $m$ 条边的简单无向图。第 $i$ 条边被染成颜色 $c_i$，该颜色为 $1$、$2$ 或 $3$ 中的一个，或者未染色（此时 $c_i = -1$）。

你需要将所有未染色的边进行染色，使得对任意三个两两相邻的顶点 $1 \leq a \lt b \lt c \leq n$，边 $a \leftrightarrow b$、$b \leftrightarrow c$ 和 $a \leftrightarrow c$ 的颜色要么互不相同，要么全部相等。若不存在满足条件的染色方案，则需判定这一点。

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.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10$）：测试用例的数量。

接下来的若干行描述各测试用例。

第一行给出两个整数 $n$ 和 $m$（$3 \leq n \leq 64$，$0 \leq m \leq \min(256, \frac{n(n-1)}{2})$）：图中顶点数和边数。

接下来的 $m$ 行中，每行包含三个整数 $a_i$、$b_i$ 和 $c_i$（$1 \leq a_i, b_i \leq n$，$a_i \ne b_i$，且 $c_i$ 的取值为 $-1$、$1$、$2$ 或 $3$），表示一条连接顶点 $a_i$ 与 $b_i$ 的边，其颜色为 $c_i$。保证不存在两条边具有完全相同的两个端点。

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$.

对于每个测试用例，输出 $m$ 个整数 $d_1, d_2, \ldots, d_m$，其中 $d_i$ 表示你最终染色方案中第 $i$ 条边的颜色。如果不存在合法的完成染色方案，则输出 $-1$。