CF1815F.OH NO1 (-2-3-4)
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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≤a,b,c≤n ).
Initially, each vertex v has a non-negative integer weight av . 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 au and av by x .
After performing all operations, the following requirement should be satisfied: if u and v are connected by an edge, then au=av .
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≤t≤105 ) — 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≤n≤106 , 1≤m≤4⋅105 ) — denoting the graph have n vertices and 3m edges.
The second line of each test case contains n integers a1,a2,…,an ( 0≤ai≤106 ) — the initial weights of each vertex.
Then m lines follows. The i -th line contains three integers ai , bi , ci ( 1≤ai<bi<ci≤n ) — denotes that three edges (ai,bi) , (bi,ci) and (ci,ai) .
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 106 and the sum of m over all test cases do not exceed 4⋅105 .
输出格式
For each test case, output m lines of 3 integers each.
The i -th line should contains three integers eab,ebc,eca ( 1≤eab,ebc,eca≤4 ), denoting the choice of value x for edges (ai,bi) , (bi,ci) and (ci,ai) 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 a1=a2 , a1=a3 , a2=a3 , 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 a1=a2 , a1=a3 , a2=a3 , and that a1=a4 , a1=a5 , a4=a5 , 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.