AT_arc215_e [ARC215E] CNOT Party

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.

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 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 Explanation 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. ### 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.