← 返回题目列表

Codeforces · 1779/F

F. Xorcerer 的石头

中文机器翻译题面 查看原题

自从米沙被指控用引擎作弊以来,他被永久禁止下棋。因此,他退休并决定成为一名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$$$ 不执行任何操作。第一张图片表示最初的树,每个节点的石头数量用绿色写在上面。当前法术所应用的更改以红色突出显示。