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 roles in this problem: “Nailoong” and “Bombloong”. Nailoong has 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 use a special one-way communication method to help Bombloong reconstruct a tree that is isomorphic to the original tree.

Isomorphic: Two trees $T_1(V_1,E_1)$ and $T_2(V_2,E_2)$ are 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 either black or white.
• 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 the 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, there is a testing tool 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$ whose length equals the number of nodes $n$ of the $i$-th tree ($col_i\in\{0,1\}$, $i=1,2,\ldots,n$), meaning Nailoong colors the $i$-th node with $col_i$. Here, $col_i=0$ means white, and $col_i=1$ means black.

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 reconstructed ($1\le u,v\le n$). You need to ensure that the tree you output is isomorphic to the tree given in 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 0

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

1 3
2 3
1 2

Hint

The two samples demonstrate the two runs in 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 color 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 to the second input will be $a_{p_1},\ldots,a_{p_T}$. Let the output trees be $t'_1,t'_2,\ldots,t'_T$ in order; the judge will compare $t_{p_i}$ and $t'_i$ to judge correctness.

How to Use the Provided Files

python3 tree_communication_testing_tool2.py data.in ./solution
python3 tree_communication_testing_tool2.py --trials 10 data.in ./solution
python3 tree_communication_testing_tool2.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 for the first input, and the trials parameter indicates the number of repeated tests.

Translated by ChatGPT 5