The power grid has been repaired, and the holographic projector has finally started successfully. As the night deepens, the holographic projections in the sky become increasingly colorful. Once everything is ready, T and S officially kick off the night's activities, inviting everyone to join in this carefully prepared light and shadow game, "Aura," which tests the tacit understanding of a pair.

Light beams in the center of the square intertwine, slowly converging into a full light tree. The light tree consists of several floating light nodes and the light paths connecting them, presenting a pure tree structure. At the start of the game, none of the paths are lit, and challengers cannot observe any lit paths. Karuha, who operates the system, will first reveal a secret number to a challenger stationed at the console. Subsequently, each light path will light up one by one, and the challenger must decide the direction of flow the moment each path appears. The partner standing at the other end of the stage must then infer this secret number solely based on the final oriented tree structure.

As participants in the celebration, Neri and Noir have decided to work together to complete this challenge. In this challenge, Neri will be stationed at the console. The system's Karuha will first provide her with two positive integers $n, s$ ($1 \le s \le 2^{n-1}$), representing the number of light nodes in the full light tree and the secret number, respectively.

Subsequently, Karuha will light up $n - 1$ light paths one by one. Neri must immediately specify the direction of flow for each path as it lights up.

For Noir, who is standing at the other end of the main stage, she will observe the final shape of the full light tree filled with flowing light. She needs to infer the secret number $s$ passed from Karuha to Neri based on the flow directions of these paths.

To win this light and shadow challenge, Neri and Noir need to formulate a strategy in advance to ensure they successfully pass this test of tacit understanding.

Implementation Details

Your program will run independently twice. The first time, it will act as Neri to decide the flow direction of each path; the second time, it will act as Noir to infer the secret number based on the final shape of the full light tree. The interactor will act as Karuha to pass information to your program.

In the first run, your program will first receive the number of light nodes $n$ and the secret number $s$ in the full light tree, and then sequentially receive $n - 1$ lit light paths. Your program needs to immediately output the specified flow direction to the interaction library to pass information to the second run.

In the second run, your program will receive information from the interactor from the first run, i.e., the flow directions of the light paths on the full light tree, and then needs to infer the secret number $s$ passed by Karuha to Neri based on this information.

Please ensure you flush the standard output buffer after every output. The flushing methods for various programming languages are as follows:

• For C/C++, use fflush(stdout) or cout.flush();
• For Java, use System.out.flush();
• For Python, use sys.stdout.flush().

Each test case contains multiple test sets. The first line of the input contains two positive integers $T, r$ ($1 \le T \le 10^4, r \in \{1, 2\}$), representing the number of test sets and the stage number. For each test set:

• If $r = 1$:

  • The first line contains two positive integers $n, s$ ($3 \le n \le 30, 1 \le s \le 2^{n-1}$), representing the number of light nodes in the full light tree and the secret number, respectively.
  • Next, $n - 1$ light paths will be lit up one by one. Each time a light path is lit, two positive integers $u, v$ ($1 \le u < v \le n$) are input, representing the two light nodes connected by the path. You must immediately output one line containing two positive integers $u, v$ or $v, u$, representing the direction of flow from $u$ to $v$ or from $v$ to $u$.
  • Note: For each light path, you must output the flow direction and flush the standard output buffer before you can continue to receive the next lit light path.

• If $r = 2$:

  • The first line contains a positive integer $n$ ($3 \le n \le 30$), representing the number of light nodes in the full light tree.
  • The next $n - 1$ lines each contain two positive integers $u, v$ ($1 \le u, v \le n$), representing a light path flowing from light node $u$ to light node $v$.
  • You must immediately output one line containing a positive integer, representing the inferred secret number $s$.
  • Note:
    • The order of test inputs within a single test case may differ from the first run.
    • For the same test set, the order in which light paths are input may be inconsistent between the two runs, but the numbering of all light nodes remains unchanged.
    • For each test set, you must output the inferred secret number $s$ and flush the standard output buffer before you can continue to receive the next test set.

Examples

Input 1

1 1
7 21
1 6
3 5
2 4
3 4
1 2
6 7

Output 1

6 1
3 5
4 2
3 4
1 2
7 6

Note

Figure 1: First test set

Input 2

1 2
9
9 8
1 2
5 6
6 7
1 4
3 5
8 3
3 4

Output 2

59

Note

Figure 2: Second test set

Testing Tool

The provided script treedir_testing_tool.py can assist you in local testing to verify the correctness of your program and print detailed interaction processes. During testing, place this script in the same directory as your compiled executable, then run the following command in the terminal:

python3 treedir_testing_tool.py [--quiet] <data_file> <program> <arguments>

• -q, --quiet: An optional parameter. After using this parameter, the test script will no longer print the detailed interaction process.
• data_file: The path to the input file provided to the test script. This file must satisfy the following format:
  • The first line contains two non-negative integers $T, seed$, representing the number of test sets and the random seed used to shuffle the test order and the order of edges within the tree. If $seed = 0$, it means no shuffling is performed.
  • The format of each test set is exactly the same as the input format for the "first run" described above.
• program: The path to your compiled executable.
• arguments: Additional command-line arguments passed to the executable.

Note:

1. The implementation of the interaction library in the test script is not exactly the same as the actual evaluation; local test results are not conclusive and are for debugging purposes only.
2. The test script only performs basic format validation on the data in data_file and does not check whether it legally satisfies the problem constraints (e.g., it will not check if $s$ satisfies the constraint $1 \le s \le 2^{n-1}$, nor will it judge whether the light paths correctly form a tree).
3. The test script does not monitor the time and space consumption of the program and cannot be used to test whether it meets the problem's time and space limits.