We are conducting research on the evolutionary process of organisms. Every organism, except for the original one, is newly born from an existing organism. In this context, the existing organism is defined as the parent organism, and the newly born organism is defined as the child organism.

Each of the $N$ organisms is assigned a unique birth number between $0$ and $N - 1$. Birth numbers are assigned in the order in which the organisms are born. Consequently, the birth number of a parent organism is always smaller than that of its child organism, and the birth number of the original organism is $0$.

The process of organisms being born through evolution can be represented as a tree structure, where organisms are vertices, the evolutionary process is represented by edges connecting parent and child organisms, and the original organism is the root. We call this tree an evolutionary tree.

For example, the figure below shows an evolutionary tree where the organism with birth number $0$ evolves to produce organisms with birth numbers $1$ and $2$; the organism with birth number $1$ evolves to produce organisms with birth numbers $3, 4,$ and $5$; the organism with birth number $2$ evolves to produce the organism with birth number $6$; and the organism with birth number $5$ evolves to produce organisms with birth numbers $7$ and $8$. In the figure below, each vertex of the tree is labeled with the birth number of the corresponding organism.

However, alas, Coach Cho Young-wook spilled coffee on your precious evolutionary tree. After the coffee spill, while the shape of the evolutionary tree and the original organism can still be identified, the birth numbers of each organism (except for the original one) can no longer be identified.

Coach Cho Young-wook hastily assigned a temporary number to each organism. The original organism was assigned the temporary number $0$, and the other $N - 1$ organisms were each assigned a unique temporary number between $1$ and $N - 1$. The temporary number of each organism may or may not be the same as its birth number. Furthermore, unlike birth numbers, there is no guarantee that the temporary number of a parent organism is smaller than that of its child organism.

For example, the figure below is the same as the evolutionary tree in the previous example, but each vertex of the tree is labeled with the temporary number of the corresponding organism.

Fortunately, a backup of the evolutionary tree was stored on Coach Cho Young-wook's laptop. However, the backup is encrypted, and Coach Cho Young-wook does not remember the password. Instead, Coach Cho Young-wook can use the backup program.

The backup program has a feature that, when given the temporary numbers of two organisms, tells you which of the two organisms has a smaller birth number. Since Coach Cho Young-wook's low-performance laptop might crash if this feature is used too many times, you must help him by writing code that recovers the birth numbers of all organisms in the evolutionary tree with as few queries as possible.

Implementation Details

You must implement the following function:

std::vector<int> recover(int N, std::vector<int> U, std::vector<int> V)

• This function is called at least once per execution.
• $U, V$: Integer arrays of size $N - 1$. For every integer $0 \le i \le N - 2$, it means that in the evolutionary tree, the organism with temporary number $U[i]$ is the parent, and the organism with temporary number $V[i]$ is the child. All $V[i]$ are distinct.
• In each function call, you must find the birth number of each organism in the evolutionary tree by calling the compare function (defined below) zero or more times, and return them in a std::vector of size $N$. If $X$ is the std::vector returned by the function, then for all $i$ ($0 \le i \le N - 1$), the birth number of the organism with temporary number $i$ must be $X[i]$.

Your program can call the following function:

int compare(int a, int b)

• $a$ and $b$ must be two integers such that $0 \le a, b \le N - 1$ and $a \neq b$.
• Returns $1$ if the birth number of the organism with temporary number $a$ is smaller than the birth number of the organism with temporary number $b$, and $0$ otherwise.

You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $2 \le N \le 10\,000$
• For all $0 \le i \le N - 2$:
  • $0 \le U[i] \le N - 1$
  • $1 \le V[i] \le N - 1$
  • $U[i] \neq V[i]$
• The given input forms a valid evolutionary tree.
• The sum of $N$ over all recover calls in a single execution is at most $10\,000$.
• In this problem, the grader is NOT adaptive. This means the birth number of each organism is fixed at the beginning of the grader's execution and does not change based on compare function calls.

Subtasks

1. (1 point) There are no organisms adjacent to three or more organisms in the evolutionary tree, and the original organism is adjacent to only one organism.
2. (7 points) $U[i] = 0$ for all $0 \le i \le N - 2$.
3. (12 points) There exists a way to assign distinct colors $c$ ($0 \le c \le N - 1$) to each organism in the evolutionary tree such that for all $1 \le i \le N - 1$, the color of the parent of the organism with color $i$ is $\lfloor \frac{i-1}{2} \rfloor$, and there exists a positive integer $k$ such that $N = 2^k - 1$. That is, the given evolutionary tree is a perfect binary tree.
4. (80 points) No additional constraints.

Each recover function call is scored as follows. The score for each subtask is the minimum score received by any recover call among the test cases within that subtask.

If the program terminates abnormally or the return value of the recover function is incorrect, it receives $0$ points.

Let $P$ be the number of permutations $X$ of $0, 1, \dots, N - 1$ that are possible under the problem conditions, such that the birth number of the organism with temporary number $i$ is $X[i]$ for $0 \le i \le N - 1$, without knowing the information about the relative order of birth numbers via the compare function or the constraints provided by the subtasks. Since the correct answer to the problem is also a possible $X$, $P$ is a positive integer. Let $Z = \lceil \log_2 P \rceil$, and let $C$ be the number of times your code called the compare function in this recover call. The score is determined by $K = \frac{C}{Z}$. If $Z = 0$ and $K$ is undefined, $K = 0$ if $C = 0$, and $K = 2025$ if $C > 0$.

• If $K > 20$, you receive $0$ points.
• If $8 < K \le 20$, you receive $(5 \times \frac{20-K}{12} + 5)$ percent of the subtask score.
• If $2.5 < K \le 8$, you receive $(50 \times \frac{8-K}{5.5} + 10)$ percent of the subtask score.
• If $1.5 < K \le 2.5$, you receive $(20 \times (2.5 - K) + 60)$ percent of the subtask score.
• If $1.4 < K \le 1.5$, you receive $(10 \times \frac{1.5-K}{0.1} + 80)$ percent of the subtask score.
• If $K \le 1.4$, you receive $100$ percent of the subtask score.

Examples

Input 1

recover(4, [0, 0, 0], [1, 2, 3])

Output 1

[0, 2, 3, 1]

Note 1

Consider the case where $N = 4, U = [0, 0, 0], V = [1, 2, 3]$. The grader calls the function as follows: recover(4, [0, 0, 0], [1, 2, 3])

The shape of the tree is as follows:

In this call: The birth number of the organism with temporary number $0$ is $0$ (no other assignment is possible). The birth number of the organism with temporary number $1$ is $2$. The birth number of the organism with temporary number $2$ is $3$. The birth number of the organism with temporary number $3$ is $1$.

Without any information, there are $6$ possible permutations for the answer: $[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1]$, so $P = 6$ and $Z = 3$.

Calling compare(1, 2) returns $1$ because $2 < 3$. Calling compare(2, 3) returns $0$ because $3 > 1$. Calling compare(1, 3) returns $0$ because $2 > 1$. Calling compare(0, 3) returns $1$ because $0 < 1$.

If you returned $[0, 2, 3, 1]$ after $4$ calls, the return value of the recover function is correct. In this case, the number of compare function calls is $4$. Since $K = \frac{C}{Z} = \frac{4}{3} \le 1.4$, you receive $100$ percent of the subtask score. This example satisfies the conditions for subtasks 2 and 4.

Sample grader

The sample grader receives the number of test cases $T$. Then, for each of the $T$ test cases, it receives the following information:

• Line 1: $N$
• Line 2: $PAR[1] \ PAR[2] \ \dots \ PAR[N - 1]$
• Line 3: $Y[0] \ Y[1] \ \dots \ Y[N - 1]$

$PAR[i]$ is the birth number of the parent of the organism with birth number $i$ in the evolutionary tree. By problem constraints, $0 \le PAR[i] < i$ is satisfied.

$Y[i]$ is the temporary number assigned to the organism with birth number $i$ in the evolutionary tree. By problem constraints, $Y[0] = 0$ and $Y$ must be a permutation of $0, 1, \dots, N - 1$.

For each test case, the sample grader constructs $U$ and $V$ according to the birth numbers and temporary numbers of each organism in the given evolutionary tree, calls the recover function, and outputs the result as follows:

• If the called compare(a, b) does not satisfy $0 \le a, b \le N - 1$, it prints Wrong Answer [1] on a single line.
• If the called compare(a, b) does not satisfy $a \neq b$, it prints Wrong Answer [2] on a single line.
• If the array returned by the recover function does not have size $N$, it prints Wrong Answer [3] on a single line.
• Otherwise, it prints the total number of compare function calls $C$ in the format C : 4 on the first line, and the elements of the return value $X$ of the recover function in order on the next line.

If Wrong Answer is printed, the sample grader terminates immediately.

Note that the correct output is one that satisfies $Y[X[i]] = i$ for all $0 \le i \le N - 1$, and the sample grader does not verify this.

Note that the sample grader may differ from the grader used in actual grading.