← 返回题目列表

Codeforces · 1616/F

F. 三色三角形

中文机器翻译题面 查看原题

给你一个简单的无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。边 $$$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$$$ 之间的边,颜色为 $$$c_i$$$。保证没有两条边共享相同的端点。

输出

对于每个测试用例,打印 $$$m$$$ 整数 $$$d_1, d_2, \ldots, d_m$$$,其中 $$$d_i$$$ 是最终着色中第 $$$i$$$ 条边的颜色。如果没有有效的方法来完成着色,则打印$$$-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