Generalized Insertion Sort

You are given a rooted tree with $N$ vertices, numbered $0, 1, \ldots, N-1$. The root is vertex $0$, and the parent of vertex $i$ ($i = 1, 2, \ldots, N-1$) is vertex $p_i$.

Initially, vertex $i$ holds the integer $a_i$. Here, $(a_0, a_1, \ldots, a_{N-1})$ is a permutation of $(0, 1, \ldots, N-1)$.

You can perform the following operation at most $25\,000$ times. The goal is to make the value at vertex $i$ equal to $i$ for every $i$.

• Choose a vertex $v$. Consider the path from vertex $0$ to $v$.
• Rotate the values on this path. For each edge $(i, p_i)$ on the path, the value at $p_i$ becomes the value at $i$ (before this operation), and the value at $v$ becomes the value at $0$ (before this operation).
• Choosing vertex $0$ does nothing.

Input is given in the following format:

$N$

$p_1$ $p_2$ ... $p_{N-1}$

$a_0$ $a_1$ ... $a_{N-1}$

In the first line, print the number of operations $Q$. In the next $Q$ lines, print the chosen vertices in order.

$2 \leq N \leq 2000$, $0 \leq p_i \leq i-1$, and $(a_0, a_1, \ldots, a_{N-1})$ is a permutation of $(0, 1, \ldots, N-1)$.

In Sample 1, after the first operation, the values at vertices $0, 1, \ldots, 4$ are $4, 0, 1, 2, 3$.

In Sample 2, after the first operation, the values at vertices $0, 1, \ldots, 4$ are $3, 1, 0, 2, 4$. After the second operation, they are $1, 0, 2, 3, 4$.