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

Memory Limit:512 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. OH NO1 (-2-3-4)time limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput
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
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
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 $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.

Input

题意翻译

### 题目描述 给定整数 $n,m$,一个长度为 $n$ 的非负整数序列 $d$,和 $m$ 个三元组 $(a_i,b_i,c_i)$,保证 $a_i<b_i<c_i$。 我们按照下列方式构造一个图: - 在这个图上建立 $n$ 个节点,编号为 $1,2,\cdots,n$。 - 对于每个整数 $i=1,2,\cdots,m$,在节点 $a_i,b_i$ 之间、$b_i,c_i$ 之间、$c_i,a_i$ 之间均各连接一条边。 注意经过上述连边过程后**两个节点之间可能存在多条边。** 接下来你需要对图上的每一条边 $(u,v)$ 都进行如下操作一次: - 选择一个整数 $x\bm{(1\leq x\leq 4)}$,然后使 $d_u,d_v$ 均加上 $x$。 在进行所有操作后,你需要使这个图满足下列要求: - 对于任意图上的边 $(u,v)$,总有 $d_u\not=d_v$。 你的任务就是给出一组能够达成要求的选择所有操作中 $x$ 的方案。 **有多组满足要求的操作方案时输出任意一组即可。可以证明在题目限制下,总是存在满足要求的操作方案。** 每个测试点包含 $t$ 组数据。 ### 输入格式 第一行输入一个整数 $t(1\leq t\leq10^5)$ 表示数据组数,接下来对于每组数据: 第一行输入两个整数 $n,m(3\leq n,\sum n\leq10^6;1\leq m,\sum m\leq4\times10^5)$。 接下来输入一行 $n$ 个整数表示序列 $d(0\leq d_i\leq10^6)$。 接下来输入 $m$ 行,其中第 $i$ 行输入三个整数 $a_i,b_i,c_i(1\leq a_i<b_i<c_i\leq n)$。 注意最终根据 $(a_i,b_i,c_i)$ 得到的图可能存在重边。 ### 输出格式 对于每组数据: 输出 $m$ 行,其中第 $i$ 行输出三个整数 $x_{ab},x_{bc},x_{ca}(1\leq x_{ab},x_{bc},x_{ca}\leq4)$ 表示对于三元组 $(a_i,b_i,c_i)$ 对应的三条边 $(a_i,b_i),(b_i,c_i),(c_i,a_i)$,你分别选择的 $x$ 的值。 有多组满足要求的操作方案时你可以输出任意一组。 可以证明一定有解。 ### 样例解释 对于第一组数据: - 操作前 $d=[0,0,0,0]$,样例输出给出了如下操作: - 对于边 $(1,2)$,选择 $x=2$,此后 $d=[2,2,0,0]$。 - 对于边 $(1,3)$,选择 $x=1$,此后 $d=[3,2,1,0]$。 - 对于边 $(2,3)$,选择 $x=3$,此后 $d=[3,5,4,0]$。 - 操作后可以发现 $d$ 中元素互不相等,因此满足题目要求。 对于第二组数据: - 操作前 $d=[0,0,0,0,0]$。 - 操作后 $d=[12,5,6,7,6]$,可以根据样例输入发现不存在连接节点 $3,5$ 的边,因此满足题目要求。 对于第三组数据: - 操作前 $d=[3,4,5,6]$。 - 操作后 $d=[19,16,17,20]$,可以发现 $d$ 中元素互不相等,因此满足题目要求。

Output

题目大意:
你有一个无向图,包含n个顶点和3m条边。图中可能包含多条边,但不包含自环。给定的边可以分为m组,每组3条边形成一个三角形。每个顶点v有一个非负整数权重a_v。对于图中的每条边(u,v),你应该执行以下操作恰好一次:选择一个1到4之间的整数x,然后将a_u和a_v都增加x。执行所有操作后,应满足:如果u和v通过一条边连接,那么a_u ≠ a_v。任务保证这总是可能的。如果有多个有效答案,输出任意一个。

输入输出数据格式:
输入:
- 第一行包含一个整数t(1 ≤ t ≤ 10^5),表示测试用例的数量。
- 每个测试用例的第一行包含两个整数n和m(3 ≤ n ≤ 10^6,1 ≤ m ≤ 4 × 10^5),表示图有n个顶点和3m条边。
- 每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n(0 ≤ a_i ≤ 10^6),表示每个顶点的初始权重。
- 接下来的m行,每行包含三个整数a_i, b_i, c_i(1 ≤ a_i < b_i < c_i ≤ n),表示三个边(a_i, b_i), (b_i, c_i)和(c_i, a_i)。

输出:
- 对于每个测试用例,输出m行,每行包含3个整数。
- 第i行应包含三个整数e_{ab}, e_{bc}, e_{ca}(1 ≤ e_{ab}, e_{bc}, e_{ca} ≤ 4),分别表示边(a_i, b_i), (b_i, c_i)和(c_i, a_i)的x值的选择。

示例输入输出:
输入:
```
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
```
输出:
```
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
```题目大意: 你有一个无向图,包含n个顶点和3m条边。图中可能包含多条边,但不包含自环。给定的边可以分为m组,每组3条边形成一个三角形。每个顶点v有一个非负整数权重a_v。对于图中的每条边(u,v),你应该执行以下操作恰好一次:选择一个1到4之间的整数x,然后将a_u和a_v都增加x。执行所有操作后,应满足:如果u和v通过一条边连接,那么a_u ≠ a_v。任务保证这总是可能的。如果有多个有效答案,输出任意一个。 输入输出数据格式: 输入: - 第一行包含一个整数t(1 ≤ t ≤ 10^5),表示测试用例的数量。 - 每个测试用例的第一行包含两个整数n和m(3 ≤ n ≤ 10^6,1 ≤ m ≤ 4 × 10^5),表示图有n个顶点和3m条边。 - 每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n(0 ≤ a_i ≤ 10^6),表示每个顶点的初始权重。 - 接下来的m行,每行包含三个整数a_i, b_i, c_i(1 ≤ a_i < b_i < c_i ≤ n),表示三个边(a_i, b_i), (b_i, c_i)和(c_i, a_i)。 输出: - 对于每个测试用例,输出m行,每行包含3个整数。 - 第i行应包含三个整数e_{ab}, e_{bc}, e_{ca}(1 ≤ e_{ab}, e_{bc}, e_{ca} ≤ 4),分别表示边(a_i, b_i), (b_i, c_i)和(c_i, a_i)的x值的选择。 示例输入输出: 输入: ``` 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 ``` 输出: ``` 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 ```

加入题单

上一题 下一题 算法标签: