Little F learned how to draw trees in art class. He drew a tree $T$ with $n$ nodes, labeled $1 \sim n$.

Because he is not satisfied with the current tree, Little F intends to use $k$ pairs of pencils and erasers to modify it. Initially, he places each pair of pencil and eraser on some node of the tree. Specifically, for $1 \le i \le k$, let the node where the pencil is located be $p_i$, and the node where the eraser is located be $e_i$. Initially, $p_i = e_i$. At any time, multiple pencils and erasers can be placed on the same node.

Each time he modifies the tree, Little F first chooses a pair of pencil and eraser. Suppose Little F chooses the $t$-th ($1 \le t \le k$) pair of pencil and eraser. He then performs the following steps:

1. Choose 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. Choose a node $y$ ($1 \le y \le n$) that is directly connected by an edge to $e_t$ (this can be an edge newly 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 must ensure that the graph obtained after each modification remains a tree.

Little F hopes to use as few pairs of pencils and erasers as possible to transform tree $T$ into another tree $T'$. You need to help Little F construct a modification scheme. Specifically, you need to determine the number of pencil and eraser pairs $k$, specify the initial positions $p_i, e_i$ ($1 \le i \le k, p_i = e_i$) for each pair, and construct a sequence of modifications $(t, x, y)$ ($1 \le t \le k, 1 \le x, y \le n$) such that after executing these modifications 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 your submitted program includes the header file paint.h, i.e., add the following code at the beginning of your program:

#include "paint.h"

You need to implement the following function in your submitted source file:

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 pencil and eraser pairs and their initial positions by calling the following function:

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

• $k$ represents the number of pencil and eraser pairs 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 pair of pencil and eraser. You must ensure that the length of $p$ is $k$, and for all $0 \le i < k$, $1 \le p_i \le n$.
• You must ensure that the interactor calls this function exactly once each time paint is called.

You can perform one modification by calling the following function:

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

• $t, x, y$ represent the index of the chosen pencil and eraser pair and the node index, respectively, with meanings as described in the problem statement. You must ensure $1 \le t \le k$, $1 \le x, y \le n$, and that the graph obtained after the modification remains a tree.
• You must ensure that each time the interactor calls paint, this function is called no more than $10^5$ times, and all calls to this function occur after calling the setting function.

Note: In any case, the execution time of the interactor will not exceed 0.2 seconds, and the memory used is fixed and will not exceed 64 MiB.

Examples

Input 1

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 1 3
2 1
3 1 4 5
4 1 5 4
5 1 3 5
6 2 2
7 4 5
8 1 5 2
9 2 3 1

Note

The sample contains two test cases.

For the first test case, 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 modification scheme is as follows:

• Initially, there is 1 pair of pencil and eraser placed at node 1.
• The first modification chooses $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 modification chooses $x = 5, y = 4$, adds edge $(4, 5)$, deletes edge $(4, 5)$, at this time $p_1 = 5, e_1 = 4$.
• The third modification chooses $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'$.

Subtasks

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

There are 20 test points in total, each containing exactly 10 test cases. For the $i$-th ($1 \le i \le 20$) test point, all test cases satisfy $n = 10i$.

Scoring

Note: You should not obtain internal information of the interactor through illegal means, such as interacting directly 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 entire problem, and runtime errors, time limit exceeded, or memory limit exceeded will result in 0 points for the corresponding test point. You can only access variables defined by yourself and variables provided by the interactor in your program; attempting to access other address spaces may lead to compilation or runtime errors.

Each time the paint function is called, if the setting or alter functions are called illegally, or if the alter function is called more than $10^5$ times, or if tree $T$ is not transformed into tree $T'$ upon return, the corresponding test point will receive 0 points.

Based on the above conditions: For each test case, let $k_{\min}$ be the minimum number of pencil and eraser pairs used, you will receive $5 \cdot 0.97^{k-k_{\min}} \cdot 0.99^{\max(\lceil m/2000 \rceil - 5, 0)}$ points. For each test point, the score obtained by the program is the minimum score among all test cases contained in that test point.