Little F learned how to draw trees in art class. He drew a tree $T$ with $n$ nodes, labeled $1 \sim n$. Since he is not very satisfied with this tree, Little F plans to use $k$ pairs of pencils and erasers to repaint it. Initially, he places each pencil and eraser on some node of the tree. Specifically, for $1 \le i \le k$, let the node where the $i$-th pencil is located be $p_i$, and the node where the $i$-th eraser is located be $e_i$, such that initially $p_i = e_i$. At any moment, multiple pencils and multiple erasers can be placed on the same node.

Each time he repaints, Little F first selects a pair of a pencil and an eraser. Suppose Little F selects the $t$-th ($1 \le t \le k$) pencil and eraser, then he performs the following steps to repaint: 1. Select any node $x$ ($1 \le x \le n$), move the pencil to node $x$, and draw the edge formed by the movement, i.e., add an edge between $p_t$ and $x$, then set $p_t \leftarrow x$; 2. Select a node $y$ ($1 \le y \le n$) that is directly connected to $e_t$ by an edge (this can be an edge drawn in the previous step), move the eraser to node $y$, and erase the edge traversed, i.e., delete the edge between $e_t$ and $y$, then set $e_t \leftarrow y$.

Of course, Little F needs to ensure that the graph remains a tree after each repainting operation. Little F hopes to use the minimum possible number of pencils and erasers to repaint tree $T$ into another tree $T'$. You need to help Little F construct a repainting scheme. Specifically, you need to determine the number of pencils and erasers $k$, specify the initial positions $p_i, e_i$ ($1 \le i \le k, p_i = e_i$) for each pair, and then construct a sequence of repainting operations $(t, x, y)$ ($1 \le t \le k, 1 \le x, y \le n$) such that after executing these operations in order, tree $T$ is transformed into tree $T'$.

Implementation Details

You do not need to, and should not, implement the main function. You must ensure that the submitted program includes the header file paint.h by adding the following code at the beginning of your program:

#include "paint.h"

You need to implement the following two functions in your submitted source file paint.cpp:

void init(int c, int t);

• $c$ and $t$ represent the test case number and the number of test groups, respectively. $c = 0$ indicates that this test case is a sample.
• For each test case, this function will be called exactly once when the program starts.

void paint(int n, std::vector<int> u, std::vector<int> v);

• $n$ represents the number of nodes in tree $T$.
• For $0 \le i < n - 1$, $u_i, v_i$ represent an edge of tree $T$.
• For $n - 1 \le i < 2n - 2$, $u_i, v_i$ represent an edge of tree $T'$.
• For each test case, this function will be called exactly $t$ times by the interactor.

You can set the number of pencils and erasers and their initial positions by calling the following function:

void setting(int k, std::vector<int> p);

• $k$ represents the number of pencils and erasers used. You must ensure $0 \le k \le 2n$.
• For $0 \le i < k$, $p_i$ represents the initial position of the $(i+1)$-th pencil and eraser. You must ensure the length of $p$ is $k$, and for all $0 \le i < k$, $1 \le p_i \le n$.
• You must ensure that for each call to paint, this function is called exactly once.

You can perform one repainting operation by calling the following function:

void alter(int t, int x, int y);

• $t, x, y$ represent the index of the selected pencil and eraser pair and the node index, respectively, with meanings as described in the description. You must ensure $1 \le t \le k$, $1 \le x, y \le n$, and that the graph remains a tree after the repainting.
• You must ensure that for each call to paint, the number of calls to this function does not exceed $10^5$, and all calls to this function are made after calling the setting function.

Note: In any case, the time required for the interactor to run will not exceed $0.2$ seconds, and the memory used is fixed and will not exceed $64$ MiB.

Examples

Input 1

0 2
5
2 3
3 1
5 1
5 4
1 4
2 3
3 1
5 3
5
4 2
1 3
5 1
1 2
2 1
3 5
3 1
4 5

Output 1

1 3
1
1 4 5
1 5 4
1 3 5
2 2
4 5
1 5 2
2 3 1

Note 1

The sample contains two test groups. For the first test group, tree $T$ contains edges $\{(1, 3), (3, 2), (1, 5), (5, 4)\}$, and tree $T'$ contains edges $\{(1, 4), (2, 3), (3, 1), (5, 3)\}$. A feasible repainting scheme is as follows: Initially, there is 1 pencil and eraser placed at node 1. The first repainting selects $x = 4, y = 5$, adds edge $(1, 4)$, deletes edge $(1, 5)$, the resulting tree contains edges $\{(1, 3), (3, 2), (5, 4), (1, 4)\}$, at this time $p_1 = 4, e_1 = 5$; The second repainting selects $x = 5, y = 4$, adds edge $(4, 5)$, deletes edge $(4, 5)$, at this time $p_1 = 5, e_1 = 4$; The third repainting selects $x = 3, y = 5$, adds edge $(5, 3)$, deletes edge $(4, 5)$, the resulting tree contains edges $\{(1, 3), (3, 2), (1, 4), (5, 3)\}$, which is tree $T'$.

Constraints

For all test cases: $1 \le t \le 10$; $4 \le n \le 200$; For all $1 \le i < n$, $1 \le u_i, v_i \le n$, and the edges form a tree; For all $1 \le i < n$, $1 \le u'_i, v'_i \le n$, and the edges form a tree; * $T$ and $T'$ are both generated independently and uniformly at random from all trees with $n$ nodes.

Subtasks

Note: You should not obtain internal information of the interactor through illegal means, such as directly interacting with standard input/output streams. Such behavior will be considered cheating. The final evaluation interactor is different from the sample interactor.

This problem is subject to the same restrictions as traditional problems; for example, compilation errors will result in 0 points for the problem, and runtime errors, time limit exceeded, or memory limit exceeded will result in 0 points for the corresponding test case. You can only access variables defined by yourself and variables provided by the interactor; attempting to access other address spaces may lead to compilation or runtime errors.

If the setting or alter functions are called illegally, or if the number of alter function calls exceeds $10^5$, the corresponding test case will receive 0 points. Based on the above conditions:

• In test cases 1 and 2, the program receives full marks if and only if after each call to paint, the tree $T$ is transformed into tree $T'$.
• In test case 3, for each test group, let $k_{\min}$ be the minimum number of pencils and erasers used:
  • If paint returns without $T$ being transformed into $T'$, receive 0 points;
  • Otherwise, receive $26 \cdot 0.97^{k-k_{\min}}$ points. The score for the program is the minimum of the scores of all test data.
• In test case 4, for each test group, let $k_{\min}$ be the minimum number of pencils and erasers used:
  • If $k \neq k_{\min}$, receive 0 points;
  • Otherwise, if paint returns without $T$ being transformed into $T'$, receive 4 points;
  • Otherwise, receive $4 + 33 \cdot 0.99^{\max(\lceil m/2000 \rceil - 5, 0)}$ points. The score for the program is the minimum of the scores of all test data.