AT_arc215_e [ARC215E] CNOT Party

長さ $ 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 $ 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ を行ってはならない。

### Sample Explanation 1 $ 1 $ つ目のテストケースについては、以下のように操作を行えばよいです。 - はじめ、 $ A = 0100 $ である。 - 操作 $ 2 $ を行う。 $ A = 1100 $ となる。 - 操作 $ 3 $ を行う。 $ A = 1110 $ となる。 - 操作 $ 1 $ を行う。 $ A = 1010 $ となる。 $ 2 $ つ目のテストケースでは、どのように操作を行っても $ A_1 $ を $ 0 $ にすることはできません。 $ 3 $ つ目のテストケースのように、 $ x_i = y_i $ である場合もありえることに注意してください。 ### 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 $ , $ 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 $ は整数