P7940 「Wdcfr-1」Alice Wins! (hard version)


**版本之间的区别在于操作的限制。** 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 队的得分）。

每个测试包含多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$。 接下来两行，分别包含长度为 $2\cdot n$ 的数组 $a$ 和数组 $b$。

对于每个测试用例，输出三行。 第一行包含一个整数，表示 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 队中一个玩家的手势。

### 解释 对于第一个测试用例，我们可以将 $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 提供。