← 返回题目列表

Codeforces · 2113/F

F. 两个数组

中文机器翻译题面 查看原题

给定两个数组 $$$a$$$ 和 $$$b$$$,长度为 $$$n$$$。您可以无限次执行以下操作:

  • 从 $$$1$$$ 到 $$$n$$$ 中选择一个整数 $$$i$$$ 并交换 $$$a_i$$$ 和 $$$b_i$$$。

令 $$$f(c)$$$ 为数组 $$$c$$$ 中不同数字的数量。求 $$$f(a) + f(b)$$$ 的最大值。另外,执行完所有操作后,输出数组 $$$a$$$ 和 $$$b$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2n$$$) — 数组 $$$a$$$ 的元素。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 2n$$$) — 数组 $$$b$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,在第一行打印一个整数 - $$$f(a) + f(b)$$$ 的最大值。

在第二行中,打印 $$$n$$$ 整数 - 执行操作后数组 $$$a$$$ 的元素。

在第三行中,打印 $$$n$$$ 整数 - 执行操作后数组 $$$b$$$ 的元素。

示例

输入
复制

3
5
1 2 4 4 4
1 3 3 5 2
7
2 2 4 4 5 5 5
1 3 3 2 1 6 6
7
12 3 3 4 5 6 4
1 2 13 8 10 13 7

输出
复制

9
1 3 4 5 2 
1 2 3 4 4 
12
2 3 4 2 1 5 6 
1 2 3 4 5 6 5 
14
12 3 13 8 10 6 4 
1 2 3 4 5 13 7 

注意

在第一个测试用例中,在应用 $$$i=2$$$、$$$i=4$$$ 和 $$$i=5$$$ 三个运算后,我们获得 $$$a = [1, 3, 4, 5, 2]$$$ 和 $$$b = [1, 2, 3, 4, 4]$$$。之后,$$$f(a) + f(b) = 5 + 4 = 9$$$。可以证明,不可能得到更大的答案。

在第二个测试用例中,应用操作后: $$$$$$f([2, 3, 4, 2, 1, 5, 6]) + f([1, 2, 3, 4, 5, 6, 5]) = 6 + 6 = 12$$$$$$