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'$，表示 Alice 修改后的 $a$ 数组。对于整数 $1$ 到 $2 \cdot n$，如果 $a_i \ne a'_i$，则表示你已经修改了 A 队中一个玩家的选择。

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

2
1
1 2
1 2
2
2 3 1 3
1 2 2 1

2
1 1
2 2
4
3 1 1 3
1 2 2 1

Hint

解释

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

对于第二个测试用例，我们可以将 $a_1$ 改为 $3$，将 $a_2$ 改为 $1$。

约束

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

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