← 返回题目列表

Codeforces · 1815/F

F. 糟糕,第一名(-2-3-4)

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

给你一个无向图,其中有 $$$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]$$$,并且所有最终权重都是不同的,这意味着没有两个相邻顶点具有相同的权重。