自从米沙被指控用引擎作弊以来,他被永久禁止下棋。因此,他退休并决定成为一名xorcerer。
有一天,在公园散步时,Misha 发现了一棵有根树,其节点编号从 $$$1$$$ 到 $$$n$$$。树的根是节点$$$1$$$。
对于每个 $$$1\le i\le n$$$,节点 $$$i$$$ 中包含 $$$a_i$$$ 石头。米莎最近在他的巫术课上学到了一个新咒语,并想测试一下。咒语包括:
- 选择某个节点 $$$i$$$ ($$$1 \leq i \leq n$$$)。
- 计算所有 $$$a_j$$$ 的按位异或 $$$x$$$,使得节点 $$$j$$$ 位于 $$$i$$$ 的子树中($$$i$$$ 属于其自己的子树)。
- 将 $$$i$$$ 子树中的所有节点 $$$j$$$ 设置为 $$$a_j$$$ 等于 $$$x$$$。
Misha 最多可以执行 $$$2n$$$ 法术,并且他想移除树上的所有石头。更正式地说,他希望 $$$a_i=0$$$ 对于每个 $$$1\leq i \leq n$$$ 成立。你能帮助他施展咒语吗?
具有 $$$n$$$ 节点的树是一个连通的非循环图,其中包含 $$$n-1$$$ 边。节点$$$i$$$的子树是所有节点$$$j$$$的集合,使得$$$i$$$位于从$$$1$$$(根)到$$$j$$$的简单路径上。我们认为 $$$i$$$ 包含在它自己的子树中。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) — 树的大小
第二行包含一个整数数组 $$$a_1,a_2,\ldots, a_n$$$ ($$$0 \leq a_i \leq 31$$$),描述每个节点最初的石子数量。
第三行包含一个整数数组 $$$p_2,p_3,\ldots, p_n$$$ ($$$1 \leq p_i \leq i-1$$$),其中 $$$p_i$$$ 表示有一条边连接 $$$p_i$$$ 和 $$$i$$$。
输出
如果没有有效的咒语序列,则输出 $$$-1$$$。
否则,在第一行输出一个整数 $$$q$$$ ($$$0 \leq q \leq 2n$$$) — 执行咒语的次数。
在第二行中输出整数序列 $$$v_1,v_2,\ldots,v_q$$$ ($$$1 \leq v_i \leq n$$$) — 第 $$$i$$$ 咒语将在节点 $$$v_i$$$ 的子树上执行。请注意顺序很重要。
如果存在多个解,则输出任意一个。您不必最小化操作次数。
示例
输入 #1
2 13 13 1
输出 #1
1 1
输入 #2
7 5 2 8 3 4 1 31 1 1 2 2 3 3
输出 #2
-1
输入 #3
9 3 31 1 2 7 30 7 3 1 1 1 1 2 5 5 3 4
输出 #3
6 3 2 3 1 2 2
注意
第三次测试的说明请参考下图。仅显示前 $$$4$$$ 咒语,因为最后 $$$2$$$ 不执行任何操作。第一张图片表示最初的树,每个节点的石头数量用绿色写在上面。当前法术所应用的更改以红色突出显示。