Recover the Node Weights

You are given a rooted tree with n nodes (numbered from 0 to n-1) where node 0 is the root. Each node i has an unknown weight p_i. The weights form a permutation of the integers 0 to n-1 with the following properties:

• p₀ = 0
• If u is the parent of v then p_u < p_v

You do not know the exact values of p_i; you only know the structure of the tree. To uncover the node weights, you are allowed to make multiple queries. Each query is of the following form:

Query: given two distinct nodes u and v (with 0 ≤ u, v < n),

• If p_u < p_v, the response is 1.
• If p_u > p_v, the response is 0.

This is an interactive problem. The interaction library is non-adaptive (i.e. all queries must be fixed in advance). You should implement the following function without writing a main function.

Function Specification

// Declaration in file header:
int compare(int u, int v);
// You are allowed to call the function:
// int compare(int u, int v);
// which satisfies:
//    if p[u] < p[v] returns 1, otherwise returns 0.
// You should implement the following function:
std::vector recover(int n, std::vector U, std::vector V);

The function recover will be called multiple times (for multiple test cases). The parameters are:

• n: the number of nodes in the tree.
• U and V: two arrays of length n-1 each representing the tree edges. For every 0 ≤ i < n-1, U[i] is the parent of V[i].

Your task is to determine the permutation p representing the weight for each node.

inputFormat

The input begins with an integer n — the number of nodes. The following two lines contain n-1 space-separated integers each. The first line represents the array U and the second line represents the array V, where for each index i (0 ≤ i < n-1), U[i] is the parent of V[i].

outputFormat

Output a permutation of length n in which the i-th integer is the weight p_i for the node i.

sample

3
0 1
1 2

0 1 2