T3 树棋

题目信息

时间限制: 1s

空间限制: 512M

输入文件: rab.in

输出文件: rab.out

题目描述

树棋的规则如下：

• 先手方执红子，后手放执蓝子，两人轮流下子
• 给出一棵以 1 节点为根的树，初始所有非叶子节点均为无色，叶节点可能是没有棋子、或者有一颗红子或蓝子
• 每次可以选择一个未被放置棋子的叶节点放置自己的棋子，直到占满所有叶节点

当所有叶节点均放置棋子后，进入结算阶段：

• 自下而上，每个非叶节点将变成所有儿子中出现最多的颜色，保证每个非叶节点都恰好有奇数个儿子
• 若最终根节点为红色，则先手获胜，否则后手获胜

现在给出一局树棋的初始棋盘，Alice 先手，Bob 后手，请问 Alice 是否有先手必胜策略？若有，请求出第一步选择哪些叶子能赢。

输入格式

第一行一个整数 $\mathrm{t}$ 表示数据组数。

每组数据第一行一个整数 $n$ 表示节点数。

第二行 $\mathrm{n}$ 个整数，第 $\mathrm{i}$ 个整数 $\mathrm{fi}$ 表示 $\mathrm{i}$ 的父亲，保证 $\mathrm{f} 1=0$。

第三行 $\mathrm{n}$ 个整数，第 $\mathrm{i}$ 个整数 $\mathrm{gi}$ 表示 $\mathrm{i}$ 的初始颜色（0 表示红色，1 表示蓝色，-1 表示无色），保证非叶节点初始都是无色，叶节点可能是无色、红色或蓝色。

输出格式

每组数据输出一行。

若 Alice 有先手必胜策略，先输出一个整数 $\mathrm{m}$ 表示第一步可以选的叶子数，接下来 $\mathrm{m}$ 个整数表示那些叶子的编号，从小到大输出。若你只知道 Alice 先手必胜，你可以只输出一行一个整数 0 以获得部分分。

否则输出一个整数 -1。

样例

样例输入 1

2
2
0 1
-1 -1
2
0 1
-1 1

样例输出 1

1 2
-1

数据范围与提示

• 对于 $20 \%$ 的数据，$\mathrm{t}=1, \mathrm{n} \leqslant 20$
• 对于 $60 \%$ 的数据，$\mathrm{n} \leqslant 2000$
• 对于 $100 \%$ 的数据，$\mathrm{t}<=10, \mathrm{n} \leqslant 100000$

若你只判断对了 Alice 是否有先手必胜策略，也可以获得该测试点一半的分数。