给你一个无向图,其中有 $$$n$$$ 个顶点和 $$$3m$$$ 个边。该图可以包含多边,但不包含自环。
该图满足以下属性:给定的边可以分为 $$$m$$$ 个 $$$3$$$ 组,这样每个组都是一个三角形。
三角形被定义为三个边 $$$(a,b)$$$、$$$(b,c)$$$ 和 $$$(c,a)$$$ 以及三个不同顶点 $$$a,b,c$$$ ($$$1 \leq a,b,c \leq n$$$)。
最初,每个顶点 $$$v$$$ 都有一个非负整数权重 $$$a_v$$$。对于图中的每条边 $$$(u,v)$$$,您应该执行以下操作一次:
- 选择 $$$1$$$ 和 $$$4$$$ 之间的整数 $$$x$$$。然后将 $$$a_u$$$ 和 $$$a_v$$$ 增加 $$$x$$$。
执行完所有操作后,应满足以下要求:如果 $$$u$$$ 和 $$$v$$$ 通过边连接,则 $$$a_u \ne a_v$$$。
可以证明,在任务的限制下这总是可能的。输出一种方法,通过输出每条边的 $$$x$$$ 的选择。很容易看出,操作顺序并不重要。如果有多个有效答案,则输出其中一个。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n \le 10^6$$$, $$$1 \le m \le 4 \cdot 10^5$$$) — 表示图有 $$$n$$$ 个顶点和 $$$3m$$$ 边。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq 10^6$$$) — 每个顶点的初始权重。
然后是 $$$m$$$ 行。第 $$$i$$$ 行包含三个整数 $$$a_i$$$、$$$b_i$$$、$$$c_i$$$ ($$$1 \leq a_i < b_i < c_i \leq n$$$) — 表示三个边 $$$(a_i,b_i)$$$、$$$(b_i,c_i)$$$ 和$$$(c_i,a_i)$$$。
请注意,图形可能包含多边:一对 $$$(x,y)$$$ 可能出现在多个三角形中。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$,所有测试用例的 $$$m$$$ 总和不超过 $$$4 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$m$$$ 行,每行包含 $$$3$$$ 个整数。
第 $$$i$$$ 行应包含三个整数 $$$e_{ab},e_{bc},e_{ca}$$$ ($$$1 \leq e_{ab}, e_{bc} , e_{ca} \leq 4$$$),表示边 $$$(a_i,分别为 b_i)$$$、$$$(b_i,c_i)$$$ 和 $$$(c_i, a_i)$$$。
示例
输入 #1
4 4 1 0 0 0 0 1 2 3 5 2 0 0 0 0 0 1 2 3 1 4 5 4 4 3 4 5 6 1 2 3 1 2 4 1 3 4 2 3 4 5 4 0 1000000 412 412 412 1 2 3 1 4 5 2 4 5 3 4 5
输出 #1
2 1 3 2 3 3 4 3 3 3 1 2 2 2 3 2 3 4 3 1 1 2 3 4 1 2 4 4 4 3 4 1 1
注意
在第一个测试用例中,初始权重为$$$[0,0,0,0]$$$。我们增加的价值如下:
- 将 $$$2$$$ 添加到顶点 $$$1$$$ 和 $$$2$$$
- 将 $$$1$$$ 添加到顶点 $$$2$$$ 和 $$$3$$$
- 将 $$$3$$$ 添加到顶点 $$$3$$$ 和 $$$1$$$
最终权重为$$$[5,3,4,0]$$$。输出有效,因为 $$$a_1 \neq a_2$$$、$$$a_1 \neq a_3$$$、$$$a_2 \neq a_3$$$,并且所有选定的值都在 $$$1$$$ 和 $$$4$$$ 之间。
在第二个测试用例中,初始权重为$$$[0,0,0,0,0]$$$。运算后的权重为$$$[12,5,6,7,6]$$$。输出有效,因为 $$$a_1 \neq a_2$$$、$$$a_1 \neq a_3$$$、$$$a_2 \neq a_3$$$ 以及 $$$a_1 \neq a_4$$$、$$$a_1 \neq a_5$$$、$$$a_4 \neq a_5$$$ 以及所有选定值都在 $$$1$$$ 之间和$$$4$$$。
在第三个测试用例中,初始权重为$$$[3,4,5,6]$$$。操作后的权重为$$$[19,16,17,20]$$$,并且所有最终权重都是不同的,这意味着没有两个相邻顶点具有相同的权重。