Problem Background

Following the clues, Renko arrived at Tanabata Slope. Without pausing to admire the scenery, her mind raced as she sought clues to another realm. Flipped statues, peculiar cracks, the hidden fifth season... This forbidden world was revealing its secrets to her.

But the first thing Renko saw was Mari, and without thinking, she grabbed Mari's hand—

Problem Description

Renko, with her keen sense of smell, realized that the method to enter the other realm must be connected to these special statues. She found that they precisely formed a tree with a peculiar shape.

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

To enter the other realm, Renko performed some operations to alter the node weights of this tree:

1. Select an edge connecting two nodes $(u, v)$, where the deeper node is $u$ (i.e., $u$ is a child of $v$), and 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 obtained a DFS sequence of the tree and recorded the node weight sequence $c$ corresponding to this DFS sequence (specifically, $c_i$ is the weight of the $i$-th node visited in the DFS process).

Unfortunately, she suddenly forgot which operations she had performed and how she had conducted the DFS. She hopes you can reconstruct any valid set of operations and the DFS sequence.

Input Format

The first line contains an integer $n$.

For the next $n$ lines: the $i$-th line contains two integers $f_i$ and $w_i$, where $f_i$ represents the parent node of node $i$ (specifically, $f_1=0$, and for other nodes, $1 \le f_i < i$), and $w_i$ represents the weight of node $i$.

The next line contains $n$ integers describing the sequence $c$, which represents the node weight sequence corresponding to Renko's DFS sequence. It is guaranteed that there exists at least one valid set of operations and DFS method to obtain sequence $c$.

Output Format

The first line contains an integer $m$, representing the number of operations you performed.

The next line contains $m$ integers, where the $i$-th integer $x_i$ represents the edge connecting node $x_i$ and its parent node $f_{x_i}$ that you selected for the $i$-th operation.

The next line contains $n$ integers describing a permutation $p$, where $p_i$ represents the $i$-th node visited in the constructed DFS sequence.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3
3 4 2
1 2 3 4

Sample Input #2

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

Sample Output #2

3
2 5 3
1 2 4 3 5

Sample Input #3

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

Sample Output #3

1
2
1 4 2 3

Sample Input #4

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

Sample Output #4

4
2 4 5 3
1 3 5 2 4

Notes/Hints

Sample Explanation

Sample #1

One possible solution is to perform operations on edges $(2,3)$, $(3,4)$, and $(1,2)$ sequentially. After these operations, the node weight sequence of the tree becomes $\{1,3,5,9\}$, and the selected DFS sequence is $\{1,2,3,4\}$.

Note that this example satisfies special property $\mathbf{A}$.

Sample #2

One possible solution is to perform operations on edges $(1,2)$, $(3,5)$, and $(1,3)$ sequentially. After these operations, the node weight sequence of the tree becomes $\{1,0,0,3,3\}$, and the selected DFS sequence is $\{1,2,4,3,5\}$.

Sample #3

One possible solution is to perform operations on edge $(1,2)$ sequentially. After these operations, the node weight sequence of the tree becomes $\{1,3,3,4\}$, and the selected DFS sequence is $\{1,4,2,3\}$.

Note that this example satisfies special property $\mathbf{B}$.

Sample #4

One possible solution is to perform operations on edges $(1,2)$, $(2,4)$, $(3,5)$, and $(1,3)$ sequentially. After these operations, the node weight sequence of the tree becomes $\{1,2,3,2,2\}$, and the selected DFS sequence is $\{1,3,5,2,4\}$.

Note that this example satisfies special property $\mathbf{C}$.

Data Range

This problem uses batched testing.

$$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{Points}} & \bm{n\le } & \textbf{\textsf{Special Properties}}&\textbf{Subtask \textsf{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 property $\mathbf{A}$: The given tree satisfies $f_i=i-1$ ($i\ne 1$).\
Special property $\mathbf{B}$: The given tree satisfies $f_i=1$ ($i\ne 1$).\
Special property $\mathbf{C}$: The given tree satisfies $w_i=1$.\
Special property $\mathbf{D}$: The given tree satisfies that the number of children of any non-leaf node is no more than $2$.

For all data, it is guaranteed that $1 \le n \le 2000$, $-10^8 \le w_i \le 10^8$, and $-10^{14} \le c_i \le 10^{14}$.

见题面 Input 部分

见题面 Output 部分