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≤N≤105 ) 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 f1f2…fN and s1s2…sN where fi represents the color of the liquid that is i units from the bottom of the first tube, and si 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≤T≤10) 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≤A≤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, 2, or 3for 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):
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 f1f2f3…fN representing the first test tube. fi∈{1,2} and f1 represents the bottom of the test tube. The subsequent line contains s1,s2,…,sN representing the second test tube.si∈{1,2} and s1 represents the bottom of the test tube.
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:
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
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:
1: 1221
2: 2211
3:
After the move "1 2":
1: 122
2: 22111
3:
After the move "1 3":
1: 1
2: 22111
3: 22
After the move "2 1":
1: 1111
2: 22
3: 22
After the move "3 2":
1: 1111
2: 2222
3:
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:
Inputs 2-6: P=1
Inputs 7-11: P=2
Inputs 12-21: No additional constraints.
Additionally, it is guaranteed that T=10 for all inputs besides the sample.
Problem credits: Suhas Nagar
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
