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 翻译