CF1815F OH NO1 (-2-3-4)

You are given an undirected graph with $ n $ vertices and $ 3m $ edges. The graph may contains multi-edges, but do not contain self loops. The graph satisfy the following property: the given edges can be divided into $ m $ groups of $ 3 $ , such that each group is a triangle. A triangle are 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 do not matter. If there are multiple valid answers, output any.

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 follows. 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 do not exceed $ 10^6 $ and the sum of $ m $ over all test cases do not exceed $ 4 \cdot 10^5 $ .

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.

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 $ 1 $ and $ 3 $ - Added $ 3 $ to vertices $ 2 $ and $ 3 $ The final weights are $ [3,5,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] $ , so all final weights are distinct, which means no two adjacent vertices have the same weight.