AT_apc001_h.Generalized Insertion Sort

给定一棵有 $N$ 个顶点的有根树。顶点编号为 $0,\ 1,\ \ldots,\ N-1$，根为顶点 $0$。顶点 $i$（$i=1,\ 2,\ \ldots,\ N-1$）的父节点为 $p_i$。

初始时，每个顶点 $i$ 上写有一个整数 $a_i$。$(a_0,\ a_1,\ \ldots,\ a_{N-1})$ 是 $0$ 到 $N-1$ 的一个排列。

你可以最多进行 $25000$ 次如下操作，从而使得每个顶点 $i$ 上的值变为 $i$。

• 选择一个顶点 $v$。考虑从顶点 $0$ 到顶点 $v$ 的路径。
• 将这条路径上的顶点的值循环右移。也就是说，对于路径上的每一条边 $(i, p_i)$，将顶点 $p_i$ 上的值写到顶点 $i$ 上，并将原来顶点 $0$ 上的值写到顶点 $v$ 上。
• 你也可以选择顶点 $0$，但在这种情况下，这个操作什么也不做。

输入从标准输入读入，格式如下：

$N$ $p_1$ $p_2$ ... $p_{N-1}$ $a_0$ $a_1$ ... $a_{N-1}$

第一行输出操作次数 $Q$。
接下来的 $Q$ 行，每行输出一次操作中选择的顶点编号。

约束条件

• $2 \leq N \leq 2000$
• $0 \leq p_i \leq i-1$
• $(a_0,\ a_1,\ \ldots,\ a_{N-1})$ 是 $0$ 到 $N-1$ 的一个排列

样例说明 1

• 第 $1$ 次操作后，顶点 $0,\ 1,\ \ldots,\ 4$ 上的值分别变为 $4,\ 0,\ 1,\ 2,\ 3$。

样例说明 2

• 第 $1$ 次操作后，顶点 $0,\ 1,\ \ldots,\ 4$ 上的值分别变为 $3,\ 1,\ 0,\ 2,\ 4$。
• 第 $2$ 次操作后，顶点 $0,\ 1,\ \ldots,\ 4$ 上的值分别变为 $1,\ 0,\ 2,\ 3,\ 4$。

由 ChatGPT 5 翻译