当前没有测试数据。

一、题目名称

试管实验（Test Tubes）

二、题目描述

贝西（Bessie）最近对化学产生了兴趣。目前，她有两种不同颜色（颜色1和颜色2）的各种液体，这些液体彼此不相溶。她有两个容量无限的试管，每个试管中都装有$N$（$1\leq N\leq10^5$）单位的这两种颜色液体的某种混合物。由于液体不相溶，一旦它们静置，就会分成不同颜色的层。因此，这两个试管可以看作字符串$f_1f_2\cdots f_N$和$s_1s_2\cdots s_N$，其中$f_i$表示距离第一个试管底部$i$单位处液体的颜色，$s_i$表示距离第二个试管底部$i$单位处液体的颜色。保证每种颜色的液体至少有一个单位。

贝西想分离这些液体，使每个试管都只含有一种颜色的所有单位液体。她有一个容量无限的空烧杯来帮助她完成这项任务。当贝西进行“倾倒”操作时，她将一个试管或烧杯顶部颜色为$i$的所有液体移动到另一个试管或烧杯中。

确定将所有液体分离到两个试管中所需的最少倾倒次数，以及完成此操作所需的一系列移动。哪个试管最终含有哪种颜色并不重要，但烧杯必须为空。

将有$T$（$1\leq T\leq10$）个测试用例，每个测试用例有一个参数$P$。

假设将液体分离到原始试管中的最少倾倒次数为$M$。

• 如果$P = 1$，仅打印$M$即可得分。
• 如果$P = 2$，打印一个整数$A$，满足$M\leq A\leq M + 5$，然后打印$A$行来构建一个使用该移动次数的解决方案。每行应包含源试管和目标试管（1表示第一个试管，2表示第二个试管，3表示烧杯）。移动前源试管必须非空，且一个试管不能倒入自身。
• 如果$P = 3$，打印$M$，然后打印一个使用该移动次数的有效构建。

三、输入格式（从终端/标准输入读取）

1. 第一行包含$T$，即测试用例的数量。对于每个测试用例，下一行包含$N$和$P$，分别表示每个试管最初填充的量和查询类型。接下来一行包含$f_1f_2f_3\cdots f_N$，表示第一个试管。$f_i\in\{1,2\}$，且$f_1$表示试管底部。随后一行包含$s_1s_2s_3\cdots s_N$，表示第二个试管。$s_i\in\{1,2\}$，且$s_1$表示试管底部。
2. 保证两个输入字符串中至少有一个1和一个2。

四、输出格式（打印输出到终端/标准输出）

对于每个测试用例，打印一个数字，表示分离试管中液体的最少倾倒次数。根据查询类型，可能还需要提供有效的构建。

五、样例输入及输出

样例输入

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

样例输出

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

解释：在前三个测试用例中，分离试管的最少倾倒次数为4。我们可以看到以下移动如何分离试管： 初始状态： 试管1：1221 试管2：2211 烧杯：空 第一次移动“1 2”后： 试管1：122 试管2：22111 烧杯：空 第二次移动“1 3”后： 试管1：1 试管2：22111 烧杯：22 第三次移动“2 1”后： 试管1：1111 试管2：22 烧杯：22 第四次移动“3 2”后： 试管1：1111 试管2：2222 烧杯：空 在最后一个测试用例中，最少倾倒次数为5。然而，由于$P = 2$，给定的6次移动的构建是有效的，因为它在最优答案的5次倾倒范围内。

六、评分规则

1. 输入2 - 6：$P = 1$。
2. 输入7 - 11：$P = 2$。
3. 输入12 - 21：无其他额外约束。
4. 此外，除样例外，所有输入保证$T = 10$。

题目来源：Suhas Nagar。