You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Bessie 最近开始对化学感兴趣。目前，她有两种不同颜色 $1$ 和 $2$ 的液体，彼此之间无法混合。她有两个无限容量的试管，各装有 $N$（$1\le N\le 10^5$）单位的这两种颜色的液体混合物。由于液体无法混合，一旦沉淀，它们就会分成不同颜色的层。因此，两个试管可以被视为两个字符串 $f_1f_2\ldots f_N$ 和 $s_1s_2\ldots s_N$，其中 $f_i$ 表示距离第一个试管底部 $i$ 单位处的液体的颜色，$s_i$ 表示距离第二个试管底部 $i$ 单位处的液体的颜色。输入保证两种颜色的液体至少各有一个单位。

Bessie 想要分离这些液体，以使得每个试管包含一种颜色的液体的所有单位。她有第三个无限容量的空烧杯来帮助她完成这一任务。当 Bessie 进行一次「倾倒」时，她将一个试管或烧杯顶部的所有颜色为 $i$ 的液体移至另一个的顶部。

求出将所有液体分离到两个试管中所需的最小的倾倒次数，以及所需的移动操作。两个试管最终包含的液体颜色不影响正确性，但烧杯必须是空的。

有 $T$（$1\le T\le 10$）个测试用例，每个测试用例有一个参数 $P$。

设将液体分离至试管中的最小倾倒次数为 $M$。

• 若 $P=1$，当你仅输出 $M$ 时可以得到分数。
• 若 $P=2$，当你输出 $A$，其中 $M\le A\le M+5$，并在以下 $A$ 行输出以该操作次数构造的一个方案时，可以得到分数。每一行包含来源试管和目标试管（$1$，$2$，或用 $3$ 表示烧杯）。操作之前，来源试管必须是非空的，并且不得将一个试管向其自身倾倒。
• 若 $P=3$，当你输出 $M$，并输出以该操作次数构造的一个方案时，可以得到分数。

输入格式

输入的第一行包含 $T$，为测试用例的数量。对于每一个测试用例，第一行包含 $N$ 和 $P$，为每个试管最初装有液体的数量以及询问类型。下一行包含 $f_1f_2f_3\ldots f_N$，表示第一个试管。$f_i\in \{1,2\}$，$f_1$ 表示试管的底部。下一行包含 $s_1s_2s_3\ldots s_N$，表示第二个试管。$s_i\in \{1,2\}$，$s_1$ 表示试管的底部。

输入保证两个字符串均包含至少一个 $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
3: 

在操作 1 2 后：

1: 122
2: 22111
3: 

在操作 1 3 后：

1: 1
2: 22111
3: 22

在操作 2 1 后：

1: 1111
2: 22
3: 22

在操作 3 2 后：

1: 1111
2: 2222
3:

在最后一个测试用例中，最小倾倒次数为 $5$。然而，由于 $P=2$，给出的 $6$ 次操作的构造也是合法的，因为它与最优解的差在 $5$ 次倾倒之内。

测试点性质

• 测试点 $2-6$：$P=1$。
• 测试点 $7-11$：$P=2$。
• 测试点 $12-21$：没有额外限制。

除此之外，输入保证除样例外的所有测试点均有 $T=10$。