Description

With keen intuition, Renko realized the method to enter this otherworld must be linked to these special Jizō statues. She discovered they formed a uniquely structured tree.

Given a rooted tree with $n$ nodes, where the root is node $1$, and each node $i$ has a weight $w_i$. For any two nodes at the same depth, they have the same number of children.

To enter the otherworld, Renko performed operations to modify the tree's node weights:

1. Select an edge connecting nodes $(u,v)$, where $u$ is the deeper node (i.e., $u$ is $v$'s child). Add $w_v$ to $w_u$.
2. This operation can be performed any number of times, but the same edge cannot be selected more than once.

After these operations, Renko derived a DFS sequence of the tree and recorded the corresponding weight sequence $c$ (specifically, $c_i$ is the weight of the $i$-th node visited in the DFS order).

Unfortunately, she forgot which operations she performed and how the DFS was conducted. Your task is to reconstruct any valid set of operations and DFS sequence.

Input Format

• The first line contains an integer $n$.
• The next $n$ lines each contain two integers $f_i$ and $w_i$:
  • $f_i$ is the parent of node $i$ (note: $f_1=0$, and for other nodes, $1 \leq f_i < i$).
  • $w_i$ is the initial weight of node $i$.
• The next line contains $n$ integers describing the target weight sequence $c$. It is guaranteed that there exists a valid set of operations and DFS order to achieve $c$.

Output Format

• The first line contains an integer $m$, the number of operations performed.
• The second line contains $m$ integers $x_1, x_2, \ldots, x_m$, where $x_i$ represents the edge between node $x_i$ and its parent $f_{x_i}$ chosen in the $i$-th operation.
• The third line contains a permutation $p$ of $n$ integers, where $p_i$ is the $i$-th node visited in your constructed DFS sequence.

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

3
3 4 2
1 2 3 4

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

3
2 5 3
1 2 4 3 5

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

1
2
1 4 2 3

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

4
2 4 5 3
1 3 5 2 4

Hint

Sample Explanations

Sample #1

One valid solution is to operate edges $(2,3)$, $(3,4)$, $(1,2)$ in order. The final weights are $\{1,3,5,9\}$, and the DFS sequence is $1,2,3,4$.
This sample satisfies Special Property A.

Sample #2

One valid solution is to operate edges $(1,2)$, $(3,5)$, $(1,3)$. The final weights are $\{1,0,0,3,3\}$, and the DFS sequence is $1,2,4,3,5$.

Sample #3

One valid solution is to operate edge $(1,2)$. The final weights are $\{1,3,3,4\}$, and the DFS sequence is $1,4,2,3$.
This sample satisfies Special Property B.

Sample #4

One valid solution is to operate edges $(1,2)$, $(2,4)$, $(3,5)$, $(1,3)$. The final weights are $\{1,2,3,2,2\}$, and the DFS sequence is $1,3,5,2,4$.
This sample satisfies Special Property C.

Constraints

Bundled testing is used.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{Points} & \bm{n \leq} & \textbf{Special Property} & \textbf{Subtask Dependencies} \cr\hline 1 & 10 & 6 & - & - \cr\hline 2 & 10 & 100 & \mathbf{A} & - \cr\hline 3 & 10 & 100 & \mathbf{B} & - \cr\hline 4 & 15 & 2 \times 10^3 & \mathbf{C} & - \cr\hline 5 & 15 & 2 \times 10^3 & \mathbf{D} & - \cr\hline 6 & 15 & 100 & - & 1,2,3 \cr\hline 7 & 25 & 2 \times 10^3 & - & 1,2,3,4,5,6 \cr\hline \end{array}$$

Special Properties:

• A: The tree satisfies $f_i = i-1$ for $i \neq 1$.
• B: The tree satisfies $f_i = 1$ for $i \neq 1$.
• C: All nodes have $w_i = 1$.
• D: All non-leaf nodes have at most 2 children.

For all data:
$1 \leq n \leq 2000$, $-10^8 \leq w_i \leq 10^8$, $-10^{14} \leq c_i \leq 10^{14}$.

---

Translated by DeepSeek R1