A15960. 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 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$ .
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.
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.
输入输出样例
输入 #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
说明/提示
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.
- 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.