/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
長さ N の 0 と 1 からなる文字列 A = A_1 A_2 \ldots A_N および B = B_1 B_2 \ldots B_N が与えられます。
M 種類の操作を行うことができます。i 種類目の操作は 1 以上 N 以下の整数の組 (x_i, y_i) によって表され、 A_{x_i} = 1 のときに A_{y_i} の値を反転させる操作です。x_i = y_i である場合もありえます。ただし、反転とは、0 を 1 に、 1 を 0 に変更する操作です。
A に対して 2N 回以内の操作を行うことによって B と等しい文字列に変換する方法が存在するか判定し、もし存在するなら 1 つ構築してください。
T 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。
制約
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- A, B は、0 と 1 からなる長さ N の文字列である。
- A \neq B
- 1 \le x_i \le N (1 \le i \le M)
- 1 \le y_i \le N (1 \le i \le M)
- 全てのテストケースにおける N, M の総和は 2 \times 10^5 以下
- T, N, M, x_i, y_i は整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N A B M x_1 y_1 x_2 y_2 \vdots x_M y_M
出力
T 個のテストケースについて順に出力せよ。
各テストケースについて、以下のように出力せよ。
条件を満たす操作列が存在しない場合、 -1 を一行に出力せよ。
条件を満たす操作列が存在する場合、操作列の長さを K 、i 番目に行う操作の番号を C_i として、
K C_1 C_2 \ldots C_K
のように出力せよ。ここで K は 2N 以下である必要がある。また、A_{x_i} = 0 のときに操作 i を行ってはならない。
入力例 1
3 4 0100 1010 4 1 2 2 1 2 3 4 3 2 10 01 1 1 2 2 01 00 3 1 1 1 2 2 1
出力例 1
3 2 3 1 -1 3 3 2 1
1 つ目のテストケースについては、以下のように操作を行えばよいです。
- はじめ、 A = 0100 である。
- 操作 2 を行う。 A = 1100 となる。
- 操作 3 を行う。 A = 1110 となる。
- 操作 1 を行う。 A = 1010 となる。
2 つ目のテストケースでは、どのように操作を行っても A_1 を 0 にすることはできません。
3 つ目のテストケースのように、x_i = y_i である場合もありえることに注意してください。
Score : 700 points
Problem Statement
You are given binary strings A = A_1 A_2 \ldots A_N and B = B_1 B_2 \ldots B_N of length N.
You can perform M types of operations. The i-th type of operation is represented by a pair of integers (x_i, y_i) with 1 \le x_i, y_i \le N, and it flips the value of A_{y_i} when A_{x_i} = 1. It is possible that x_i = y_i. Here, flipping means changing 0 to 1 or 1 to 0.
Determine whether it is possible to convert A into a string equal to B by performing at most 2N operations on A, and if so, construct one such way.
You are given T test cases; solve each one.
Constraints
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- A and B are binary strings of length N.
- A \neq B
- 1 \le x_i \le N (1 \le i \le M)
- 1 \le y_i \le N (1 \le i \le M)
- The sum of N and M over all test cases is at most 2 \times 10^5.
- T, N, M, x_i, y_i are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N A B M x_1 y_1 x_2 y_2 \vdots x_M y_M
Output
Output for the T test cases in order.
For each test case, output as follows.
If no sequence of operations satisfying the condition exists, output -1 on a single line.
If a sequence of operations satisfying the condition exists, let K be the length of the sequence of operations and C_i be the index of the i-th operation performed, and output as follows:
K C_1 C_2 \ldots C_K
Here, K must be at most 2N, and operation i must not be performed when A_{x_i} = 0.
Sample Input 1
3 4 0100 1010 4 1 2 2 1 2 3 4 3 2 10 01 1 1 2 2 01 00 3 1 1 1 2 2 1
Sample Output 1
3 2 3 1 -1 3 3 2 1
For the first test case, you can perform the operations as follows.
- Initially, A = 0100.
- Perform operation 2. Now, A = 1100.
- Perform operation 3. Now, A = 1110.
- Perform operation 1. Now, A = 1010.
For the second test case, no matter what operations are performed, it is impossible to make A_1 equal to 0.
Note that, as in the third test case, x_i = y_i is possible.