CF1815F.OH NO1 (-2-3-4)

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.

你被给定一个包含 $n$ 个顶点和 $3m$ 条边的无向图。该图可能包含重边，但不包含自环。

该图满足如下性质：所给的边可以被划分为 $m$ 组，每组恰好包含 3 条边，且每组构成一个三角形。

所谓三角形，是指对某三个互不相同的顶点 $a,b,c$（其中 $1 \leq a,b,c \leq n$），存在三条边 $(a,b)$、$(b,c)$ 和 $(c,a)$。

初始时，每个顶点 $v$ 都有一个非负整数权值 $a_v$。对于图中的每条边 $(u,v)$，你需要恰好执行一次如下操作：

• 选择一个介于 $1$ 到 $4$ 之间的整数 $x$；然后将 $a_u$ 和 $a_v$ 同时增加 $x$。

在执行完所有操作后，需满足如下要求：若顶点 $u$ 与 $v$ 之间存在一条边，则必须有 $a_u \ne a_v$。

在本题约束下，可以证明这样的方案总是存在的。请输出一种可行方案，即为每条边指定所选的 $x$ 值。显然，操作的执行顺序无关紧要。若存在多种合法答案，输出任意一种即可。

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 \lt b_i \lt 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$.

第一行包含一个整数 $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 \lt b_i \lt 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$。

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.

对每个测试用例，输出 $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)$ 上所选择的值 $x$。

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.

在第一个测试用例中，初始权重为 $[0,0,0,0]$。我们按如下方式添加了数值：

• 向顶点 $1$ 和 $2$ 各添加 $2$；
• 向顶点 $2$ 和 $3$ 各添加 $1$；
• 向顶点 $3$ 和 $1$ 各添加 $3$。

最终权重为 $[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]$，且所有最终权重互不相同，这意味着任意两个相邻顶点的权重均不相等。