310911: CF1907G. Lights

G. Lightstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

In the end of the day, Anna needs to turn off the lights in the office. There are $n$ lights and $n$ light switches, but their operation scheme is really strange. The switch $i$ changes the state of light $i$, but it also changes the state of some other light $a_i$ (change the state means that if the light was on, it goes off and vice versa).

Help Anna to turn all the lights off using minimal number of switches, or say it is impossible.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Descriptions of test cases follow.

The first line of each test case contains the integer $n$ ($2 \le n \le 10^5$) — the number of lights.

The second line of each test case contains the string of $n$ characters, the initial state of the lights. Character "0" means that the corresponding light is off, and "1" means that it is on.

The third line of each test case contains $n$ integers $a_i$ ($1 \le a_i \le n$, $a_i \neq i$) — the switch $i$ changes the states of light $i$ and light $a_i$.

It is guaranteed that sum of $n$ over all test cases does not exceed $2 \cdot 10^5$

Output

For each test case output the integer $k$, the minimal number of switches to use, then in the separate line output the list of $k$ switches.

If it is impossible to turn off all the lights, output single integer $-1$.

ExampleInput

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

Output

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 

题目大意：
这个题目是关于开关和灯泡的问题。有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。

示例输入输出已在题目中给出。题目大意： 这个题目是关于开关和灯泡的问题。有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。 示例输入输出已在题目中给出。