Problem Description

This is a communication problem. In this problem, your program will be run twice. Between the two runs, all variables stored in memory will be lost, but the information obtained in the first run may be very important for solving the problem correctly in the second run.

There are two characters in this problem: “Nailoong” and “Bombloong”. Nailoong knows the complete structure of a tree with $n$ nodes, while Bombloong only knows the number of nodes $n$. Since Bombloong is locked up by an evil little leopard, Nailoong can only help Bombloong restore a tree isomorphic to the original one through a special one-way communication method.

Isomorphic: Two trees $T_1(V_1,E_1)$ and $T_2(V_2,E_2)$ are called isomorphic if and only if there exists a bijection $f:V_1\to V_2$ such that for all $\{u,v\}\in E_1$, $\{f(u),f(v)\}\in E_2$.

The communication rules are as follows:

• Nailoong needs to color each node of the tree as black, white, or gray.
• The little leopard will generate a sequence according to the following code.
• Nailoong can only send this sequence $c_1,c_2,\ldots,c_{2n-1}$ of length $2n-1$ to Bombloong.

Nailoong cannot directly send node labels to Bombloong; she can only send the sequence $c$. After receiving $n$ and the sequence $c$, Bombloong needs to construct and output a tree that is isomorphic to Nailoong’s tree.

Communication Protocol

For each test point, the contestant’s program will be run twice. In the provided files, a testing tool is included for local debugging.

First Run

In the first run, you will play the role of “Nailoong”.

Input

The first line contains a string first, which allows your program to recognize that this is the first run.

The second line contains an integer $T$ ($1\le T\le 10^4$), the number of test cases.

For each test case, the first line contains an integer $n$ ($2\le n\le 2\times 10^5$), the number of nodes in the tree.

The next $n-1$ lines each contain two integers $u,v$ ($1\le u,v\le n$), representing an edge of the tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$.

Output

Your output should contain $T$ lines. The $i$-th line contains a sequence $col_1,col_2,\ldots,col_n$ of length equal to the number of nodes $n$ in the $i$-th tree ($col_i\in\{0,1,2\}$, $i=1,2,\ldots,n$), meaning that Nailoong colors the $i$-th node with $col_i$. Here, $col_i=0$ means white, $col_i=1$ means black, and $col_i=2$ means gray.

Second Run

In the second run, you will play the role of “Bombloong”.

Input

The first line contains a string second, which allows your program to recognize that this is the second run.

The second line contains an integer $T$ ($1\le T\le 10^4$), the number of test cases.

For each test case, the first line contains an integer $n$ ($2\le n\le 2\times 10^5$), the number of nodes in the tree.

The next line contains $2n-1$ integers, representing the sequence generated by the judge based on Nailoong’s coloring.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$.

Output

For the $i$-th test case, let the input number of nodes be $n$. Output $n-1$ lines, each containing two integers $u,v$, representing an edge of the tree you restored ($1\le u,v\le n$). You need to guarantee that the output tree is isomorphic to the tree in the input of the first run.

Input Format

See the communication protocol in the problem description.

Output Format

See the communication protocol in the problem description.

first
2
2
1 2
3
1 2
2 3

0 1
0 1 2

second
2
3
0 1 2 1 0
2
0 1 0

1 3
2 3
1 2

Hint

The two samples demonstrate the two runs within the same test point.

Note that if the trees in the first input are $t_1,\ldots,t_T$ in order, and the output color sequences are $col_1,\ldots,col_T$. Let the sequences obtained by the judge from $t_i,col_i$ ($1\le i\le T$) be $a_i$. The judge will randomly generate a permutation $p_1,\ldots,p_T$ of $1\sim T$, and then the order sent in the second input will be $a_{p_1},\ldots,a_{p_T}$. The output trees are $t'_1,t'_2,\ldots,t'_T$ in order, and the judge will compare $t_{p_i}$ with $t'_i$ for judging.

How to Use the Provided Files

python3 tree_communication_testing_tool1.py data.in ./solution
python3 tree_communication_testing_tool1.py --trials 10 data.in ./solution
python3 tree_communication_testing_tool1.py data.in python3 solution.py

Here, solution or solution.py is the executable compiled from C/C++ or the Python source code, data.in is the data from the first input, and the trials parameter indicates the number of repeated tests.

Translated by ChatGPT 5