CF1616F Tricolor Triangles

给定一个包含 $n$ 个顶点和 $m$ 条边的简单无向图。第 $i$ 条边被染成颜色 $c_i$，其中 $c_i$ 可以是 $1$、$2$、$3$ 中的一个，或者未染色（此时 $c_i = -1$）。 你需要给所有未染色的边染色，使得对于任意三个两两相邻的顶点 $1 \leq a < b < c \leq n$，边 $a \leftrightarrow b$、$b \leftrightarrow c$ 和 $a \leftrightarrow c$ 的颜色要么两两不同，要么全部相同。如果不存在这样的染色方案，你需要判断出来。

输入的第一行为一个整数 $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$ 的边及其颜色。保证没有两条边有相同的端点。

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

由 ChatGPT 4.1 翻译