← 返回题目列表

Codeforces · 1907/G

G. 灯

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

一天结束时,安娜需要关掉办公室的灯。有$$$n$$$灯和$$$n$$$灯开关,但它们的操作方案确实很奇怪。开关 $$$i$$$ 改变了灯 $$$i$$$ 的状态,但它也改变了其他灯 $$$a_i$$$ 的状态(改变状态意味着如果灯亮了,它就会熄灭,反之亦然)。

帮助安娜使用最少数量的开关关闭所有灯,或者说这是不可能的。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 灯光数量。

每个测试用例的第二行包含 $$$n$$$ 字符的字符串,即灯的初始状态。字符“0”表示对应灯灭,“1”表示对应灯亮。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le n$$$, $$$a_i \neq i$$$) - 开关 $$$i$$$ 改变灯 $$$i$$$ 和灯 $$$a_i$$$ 的状态。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$

输出

对于每个测试用例,输出整数 $$$k$$$,即要使用的开关的最小数量,然后在单独的行中输出 $$$k$$$ 开关的列表。

如果无法关闭所有灯,则输出单个整数$$$-1$$$。

示例

输入 #1

8
5
11101
4 3 4 2 2
2
10
2 1
10
0000000011
9 10 10 7 10 9 9 9 10 2
10
1000111101
9 3 8 9 2 1 3 7 2 7
10
0001101010
5 7 6 10 8 3 6 6 2 2
10
0101100010
8 7 7 9 9 4 1 4 2 7
10
1010111010
7 9 10 7 7 2 8 6 10 4
10
1110000001
3 10 10 1 10 8 6 3 2 1

输出 #1

3
1 5 3 
-1
1
9 
5
5 6 10 2 3 
6
4 9 5 10 8 7 
3
5 4 9 
6
1 3 5 9 7 8 
2
2 1