Description

版本之间的区别在于操作的限制。

Alice 是一个可爱的女孩，她有很多玩偶。

有 $4\cdot n$ 个玩偶在玩“石头剪刀布”。它们被分成两个队伍：A 队和 B 队。每个队伍包含 $2\cdot n$ 个玩偶。

游戏将进行总共 $2\cdot n$ 轮。在第 $i$ 轮中，A 队的第 $i$ 个玩偶将与 B 队的第 $i$ 个玩偶对战。如果 A 队的玩偶赢了，A 队将获得 $1$ 分。如果输了，A 队将失去 $1$ 分。如果平局，A 队将不获得分数。

Alice 知道所有玩偶在这场游戏中的选择。具体来说，她使用两个数组 $a$ 和 $b$ 来表示两个队伍中玩偶的选择。$a_i$ 表示 A 队第 $i$ 个玩偶的选择，$b_i$ 表示 B 队第 $i$ 个玩偶的选择。在这个问题中，我们用 $1$ 表示石头，$2$ 表示剪刀，$3$ 表示布。

现在对于每个队伍，Alice 想要改变恰好 $n$ 个玩偶的选择，以使 A 队的得分尽可能高。

找出 A 队的最大得分及其构造方法。如果有多个答案，输出任意一个（你仍然需要最大化 A 队的得分）。

Input Format

每个测试包含多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$。

接下来两行，分别包含长度为 $2\cdot n$ 的数组 $a$ 和数组 $b$。

Output Format

对于每个测试用例，输出三行。

第一行包含一个整数，表示 A 队的最大得分。

第二行包含长度为 $2\cdot n$ 的数组 $a'$，表示修改后的 $a$ 数组。对于整数 $1$ 到 $2\cdot n$，如果 $a_i \ne a'_i$，则表示你已经修改了 A 队中一个玩家的手势。

第三行包含长度为 $2\cdot n$ 的数组 $b'$，表示修改后的 $b$ 数组。对于整数 $1$ 到 $2\cdot n$，如果 $b_i \ne b'_i$，则表示你已经修改了 B 队中一个玩家的手势。

1
1
1 2
1 2

2
1 1
2 2

Hint

解释

对于第一个测试用例，我们可以将 $a_2$ 改为 $1$，将 $b_1$ 改为 $2$。然后 A 队可以得到 $2$ 分。可以证明这是 A 队可以获得的最大分数。

约束

$1\le T,n \le 10^5; 1\le a_i,b_i \le 3$。所有测试用例的 $n$ 之和 $\le 10^5$。

题面翻译由 ChatGPT-4o 提供。