OH NO1 (-2-3-4)
Contest: Codeforces Round 865 (Div. 1)
Difficulty rating: 3500
Tags: constructive algorithms, graphs, math

You are given an undirected graph with $$$n$$$ vertices and $$$3m$$$ edges. The graph may contain multi-edges, but does not contain self-loops.

The graph satisfies the following property: the given edges can be divided into $$$m$$$ groups of $$$3$$$, such that each group is a triangle.

A triangle is defined as three edges $$$(a,b)$$$, $$$(b,c)$$$ and $$$(c,a)$$$ for some three distinct vertices $$$a,b,c$$$ ($$$1 \leq a,b,c \leq n$$$).

Initially, each vertex $$$v$$$ has a non-negative integer weight $$$a_v$$$. For every edge $$$(u,v)$$$ in the graph, you should perform the following operation exactly once:

- Choose an integer $$$x$$$ between $$$1$$$ and $$$4$$$. Then increase both $$$a_u$$$ and $$$a_v$$$ by $$$x$$$.

After performing all operations, the following requirement should be satisfied: if $$$u$$$ and $$$v$$$ are connected by an edge, then $$$a_u \ne a_v$$$.

It can be proven this is always possible under the constraints of the task. Output a way to do so, by outputting the choice of $$$x$$$ for each edge. It is easy to see that the order of operations does not matter. If there are multiple valid answers, output any.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 10^6$$$, $$$1 \le m \le 4 \cdot 10^5$$$) — denoting the graph have $$$n$$$ vertices and $$$3m$$$ edges.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq 10^6$$$) — the initial weights of each vertex.

Then $$$m$$$ lines follow. The $$$i$$$-th line contains three integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ ($$$1 \leq a_i < b_i < c_i \leq n$$$) — denotes that three edges $$$(a_i,b_i)$$$, $$$(b_i,c_i)$$$ and $$$(c_i,a_i)$$$.

Note that the graph may contain multi-edges: a pair $$$(x,y)$$$ may appear in multiple triangles.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output format:
For each test case, output $$$m$$$ lines of $$$3$$$ integers each.

The $$$i$$$-th line should contains three integers $$$e_{ab},e_{bc},e_{ca}$$$ ($$$1 \leq e_{ab}, e_{bc} , e_{ca} \leq 4$$$), denoting the choice of value $$$x$$$ for edges $$$(a_i, b_i)$$$, $$$(b_i,c_i)$$$ and $$$(c_i, a_i)$$$ respectively.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the initial weights are $$$[0,0,0,0]$$$. We have added values as follows:

- Added $$$2$$$ to vertices $$$1$$$ and $$$2$$$
- Added $$$1$$$ to vertices $$$2$$$ and $$$3$$$
- Added $$$3$$$ to vertices $$$3$$$ and $$$1$$$

The final weights are $$$[5,3,4,0]$$$. The output is valid because $$$a_1 \neq a_2$$$, $$$a_1 \neq a_3$$$, $$$a_2 \neq a_3$$$, and that all chosen values are between $$$1$$$ and $$$4$$$.

In the second test case, the initial weights are $$$[0,0,0,0,0]$$$. The weights after the operations are $$$[12,5,6,7,6]$$$. The output is valid because $$$a_1 \neq a_2$$$, $$$a_1 \neq a_3$$$, $$$a_2 \neq a_3$$$, and that $$$a_1 \neq a_4$$$, $$$a_1 \neq a_5$$$, $$$a_4 \neq a_5$$$, and that all chosen values are between $$$1$$$ and $$$4$$$.

In the third test case, the initial weights are $$$[3,4,5,6]$$$. The weights after the operations are $$$[19,16,17,20]$$$, and all final weights are distinct, which means no two adjacent vertices have the same weight.

Example input:
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

Example output:
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

Editorial:
There are two key ideas:
1. Go through from vertex $$$1$$$ through $$$n$$$ and decided their final weights in this order. When deciding the weights for $$$v$$$ , make sure it is different from $$$w$$$ if $$$w < v$$$ and $$$v$$$ is adjacent to $$$w$$$. Ignore vertices $$$x$$$ where $$$x$$$ is adjacent to $$$v$$$ but have $$$x > v$$$.
2. If there are at least $$$d+1$$$ options to take from, and $$$d$$$ of them are not available, we can take the last option.
Let's try to decide the final weights of $$$1$$$ through $$$n$$$ in this order. For a triangle $$$a<b<c$$$, we call $$$a$$$ the first vertex, $$$b$$$ the second vertex, $$$c$$$ the third vertex. Consider each triangle individually, if we can achieve the following task then we are done: By only adjusting edges of this triangle:
• There is at least one option for the first vertex
• After fixing a particular option for the first vertex, there are at least two options for the the second vertex
• After fixing particular options for the first two vertices, there are at least three options for the third vertex
To see this is enough: Suppose a vertex $$$v$$$ is in $$$A$$$ triangles as the first vertex, $$$B$$$ triangles as the second vertex, and $$$C$$$ triangles as the third vertex. It is not difficult to see $$$v$$$ have exactly $$$B + 2 \times C$$$ neighbours that are of smaller index, and there are at least $$$B+ 2\times C+ 1$$$ options.
Finally, by using the following specific edge weights, the goal can be achieved:
• $$$1,4,4$$$ gives weights $$$5,5,8$$$
• $$$2,3,3$$$ gives weights $$$5,5,6$$$
• $$$3,2,2$$$ gives weights $$$5,5,4$$$
• $$$1,4,3$$$ gives weights $$$5,4,7$$$
• $$$2,3,2$$$ gives weights $$$5,4,5$$$
• $$$3,2,1$$$ gives weights $$$5,4,3$$$
These numbers aren't exactly just completely random. You can see that they are composed of two components: A $$$(+1,-1,-1)$$$ part and a $$$(0,0,-1)$$$ part. Upto two copies of the first option and upto one copy of the second option have been used.
This is a special case of 1-2-3 conjecture, which states that the above statement holds for arbitrary graph and using only the weights 1,2,3 (and no 4). Recently (March 2023) it has a claimed proof. The claimed algorithm is far from a linear time algorithm however.