← 返回题目列表

Codeforces · 1530/D

D. 秘密圣诞老人

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

每年 12 月,VK 都会为其员工举办名为“秘密圣诞老人”的活动。事情是这样的。

编号从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 员工参加了该活动。每个员工$$$i$$$ 都分配有不同的员工$$$b_i$$$,员工$$$i$$$ 必须向其制作一份新年礼物。每个员工都被分配给另一名员工,并且没有人被分配给自己(但两个员工可以被分配给彼此)。形式上,所有 $$$b_i$$$ 必须是 $$$1$$$ 和 $$$n$$$ 之间的不同整数,并且对于任何 $$$i$$$,$$$b_i \ne i$$$ 必须成立。

分配通常是随机生成的。今年,作为一项实验,所有活动参与者都被问及他们希望向谁赠送礼物。每个员工 $$$i$$$ 都表示他们希望给员工 $$$a_i$$$ 送一份礼物。

找到一个有效的分配$$$b$$$,以最大化员工满足愿望的数量。

输入

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

每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) - 活动参与者的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$; $$$a_i \ne i$$$) - 员工的愿望,按从 $$$1$$$ 到 $$$n$$$ 的顺序排列。

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

输出

对于每个测试用例,打印两行。

在第一行中,打印一个整数 $$$k$$$ ($$$0 \le k \le n$$$) — 作业中已实现愿望的数量。

在第二行中,打印 $$$n$$$ 不同的整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$; $$$b_i \ne i$$$) - 分配给员工 $$$1, 2, \ldots, n$$$ 的员工数量。

$$$k$$$ 必须等于 $$$i$$$ 的值数量,使得 $$$a_i = b_i$$$,并且必须尽可能大。如果有多个答案,请打印其中一个。

示例

输入 #1

2
3
2 1 2
7
6 4 6 2 4 5 6

输出 #1

2
3 1 2
4
6 4 7 2 3 5 1

注意

在第一个测试用例中,存在两个有效的赋值:$$$[3, 1, 2]$$$ 和 $$$[2, 3, 1]$$$。前一个任务满足了两个愿望,而后一个任务只满足了一个愿望。因此,$$$k = 2$$$,唯一正确答案是$$$[3, 1, 2]$$$。