G. Nailoong vs. Bombloong 3.1
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 during the first run may be crucial for solving the problem during the second run.

There are two characters in this problem: "Nailoong" and "Bombloong".

Nailoong has complete structural information about a tree with $$$n$$$ vertices, while Bombloong only knows the number of vertices $$$n$$$. Since Bombloong has been imprisoned by the evil little leopard, Nailoong can only help Bombloong reconstruct a tree that is isomorphic to the original tree through a special one-way communication method.

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 every $$$\{u,v\}\in E_1$$$, $$$\{f(u),f(v)\}\in E_2$$$.

The rules of communication are as follows:

  • Nailoong must color every vertex of the tree either black, white, or grey;
  • the little leopard generates a sequence according to the code below;
  • Nailoong can send only the sequence $$$c_1,c_2,\dots,c_{2n-1}$$$ of length $$$2n-1$$$ to Bombloong.
function DFS(u, parent)
    append u to tour
    for v in vertices adjacent to u
        if v is not parent, then
            DFS(v, u)
            append u to tour
        Endif
    Endfor
Endfunction

function GenerateSequence(T, color)
    tour <- empty sequence
    root <- the starting vertex chosen by the leopard
    DFS(root, NIL)
    c <- empty sequence
    for v in tour
        append color[v] to c
    Endfor
    Return c
Endfunction

Nailoong cannot directly send the vertex indices to Bombloong; she can only send the sequence $$$c$$$. After receiving $$$n$$$ and the sequence $$$c$$$, Bombloong must construct and output a tree isomorphic to Nailoong's tree.

Communication Protocol

In each test, the contestant's program will be run twice. A testing tool is provided in the handout files for local debugging.

First Run

In the first run, you play the role of "Nailoong".

Input

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

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

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

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

It is guaranteed that the sum of $$$n$$$ over all testcases 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,\dots,col_n$$$ of length $$$n$$$, where each $$$col_i\in\{\mathbf{0,1,2}\}$$$ $$$(i=1,2,\dots,n)$$$, denoting the color assigned by Nailoong to the $$$i$$$-th vertex. $$$col_i=0$$$ denotes white, $$$col_i=1$$$ denotes black, and $$$col_i=2$$$ denotes grey.

Second Run

In the second run, you play the role of "Bombloong".

Input

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

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

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

The next line contains $$$2n-1$$$ integers $$$c_1,c_2,\dots,c_{2n-1}$$$, denoting the sequence generated by the judge according to Nailoong's coloring.

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

Output

For the $$$i$$$-th test case, let the input number of vertices be $$$n$$$.

Output $$$n-1$$$ lines, each containing two integers $$$u,v$$$ $$$(1\le u,v\le n)$$$, denoting an edge of the reconstructed tree.

You must ensure that the output tree is isomorphic to the tree given in the first run.

Note

The two samples in the PDF statement included in the contest materials correspond to the two runs of the same test case.

Suppose the trees in the first input are $$$t_1,t_2,\dots,t_T$$$ in order, and Nailoong outputs the corresponding colorings $$$col_1,col_2,\dots,col_T$$$, where every vertex is assigned one of the three colors $$$0,1,2$$$.

For each $$$1\le i\le T$$$, let $$$a_i$$$ be the sequence generated by the little leopard from the tree $$$t_i$$$ and the coloring $$$col_i$$$.

The evaluator then randomly generates a permutation $$$p_1,p_2,\dots,p_T$$$ of $$$1,2,\dots,T$$$ and gives the sequences

$$$$$$ a_{p_1},a_{p_2},\dots,a_{p_T} $$$$$$

to Bombloong in this order during the second run.

Suppose the trees output by Bombloong are $$$t'_1,t'_2,\dots,t'_T$$$. For every $$$1\le i\le T$$$, the evaluator checks whether $$$t'_i$$$ is isomorphic to $$$t_{p_i}$$$.

How to Use the Handout 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 is a compiled C/C++ executable, and solution.py is a Python source file.

The file data.in contains the input for the first run.

The optional parameter --trials specifies the number of independent simulations. In different simulations, the little leopard may choose different DFS starting vertices and different orders in which adjacent vertices are visited.