当前没有测试数据。

一、Problem Name

Test Tubes

二、Problem Description

Bessie has recently gotten into chemistry. At the moment, she has two different colors 1 and 2 of various liquids that don't mix well with one another. She has two test tubes of infinite capacity filled with $N$ ($1\leq N\leq10^5$) units each of some mixture of liquids of these two colors. Because the liquids don’t mix, once they settled, they divided into layers of separate colors. Because of this, the two tubes can be viewed as strings $f_1f_2\cdots f_N$ and $s_1s_2\cdots s_N$ where $f_i$ represents the color of the liquid that is $i$ units from the bottom of the first tube, and $s_i$ represents the color of the liquid that is $i$ units from the bottom of the second tube. It is guaranteed that there is at least one unit of each color of liquid.

Bessie wants to separate these liquids so that each test tube contains all units of one color of liquid. She has a third empty beaker of infinite capacity to help her in this task. When Bessie makes a "pour", she moves all liquid of color $i$ at the top of one test tube or beaker into another.

Determine the minimum number of pours to separate all the liquid into the two test tubes, and the series of moves needed to do so. It does not matter which test tube ends up with which color, but the beaker must be empty.

There will be $T$ ($1\leq T\leq10$) test cases, with a parameter $P$ for each test case.

Suppose the minimum number of pours to separate the liquids into the original tubes is $M$.

• If $P = 1$, you will receive credit if you print only $M$.
• If $P = 2$, you will receive credit if you print an integer $A$ such that $M\leq A\leq M + 5$, followed by $A$ lines that construct a solution with that number of moves. Each line should contain the source and the destination tube (1 for the first tube, 2 for the second tube, or 3 for the beaker). The source tube must be nonempty before the move and a tube may not be poured into itself.
• If $P = 3$, you will receive credit if you print $M$, followed by a valid construction using that number of moves.

三、Input Format (input arrives from the terminal / stdin)

1. The first line contains $T$, the number of test cases. For each test case, the next line contains $N$ and $P$ representing the amount each test tube is initially filled to, and the query type. The following line contains $f_1f_2f_3\cdots f_N$ representing the first test tube. $f_i\in\{1,2\}$ and $f_1$ represents the bottom of the test tube. The subsequent line contains $s_1s_2s_3\cdots s_N$ representing the second test tube. $s_i\in\{1,2\}$ and $s_1$ represents the bottom of the test tube.
2. It is guaranteed that there will be at least one 1 and one 2 across both input strings.

四、Output Format (print output to the terminal / stdout)

For each test case, you will print a single number representing the minimum pours to separate the liquid in the test tubes. Depending on the query type, you may also need to provide a valid construction.

五、Sample Input and Output

Sample Input

6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
1222

Sample Output

4
4
1 2
1 3
2 1
3 2
4
1 2
1 3
2 1
3 2
1
2 1
5
2 3
1 2
1 3
1 2
3 1
6
2 3
1 2
1 3
1 2
2 1
3 2

Explanation: In the first three test cases, the minimum number of pours to separate the tubes is 4. We can see how the following moves separate the test tubes: Initial state: Tube 1: 1221 Tube 2: 2211 Beaker: After the move "1 2": Tube 1: 122 Tube 2: 22111 Beaker: After the move "1 3": Tube 1: 1 Tube 2: 22111 Beaker: 22 After the move "2 1": Tube 1: 1111 Tube 2: 22 Beaker: 22 After the move "3 2": Tube 1: 1111 Tube 2: 2222 Beaker: In the last test case, the minimum amount of pours is 5. However, since $P = 2$, the given construction with 6 moves is valid since it is within 5 pours from the optimal answer.

六、Scoring Rules

1. Inputs 2 - 6: $P = 1$.
2. Inputs 7 - 11: $P = 2$.
3. Inputs 12 - 21: No additional constraints.
4. Additionally, it is guaranteed that $T = 10$ for all inputs besides the sample.

Problem credits: Suhas Nagar.