You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目信息

时间限制: 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 是否有先手必胜策略，也可以获得该测试点一半的分数