给你一个简单的无向图,其中有 $$$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