Secret Santa
Contest: Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine))
Difficulty rating: 1600
Tags: constructive algorithms, flows, graphs, greedy, math

Every December, VK traditionally holds an event for its employees named "Secret Santa". Here's how it happens.

$$$n$$$ employees numbered from $$$1$$$ to $$$n$$$ take part in the event. Each employee $$$i$$$ is assigned a different employee $$$b_i$$$, to which employee $$$i$$$ has to make a new year gift. Each employee is assigned to exactly one other employee, and nobody is assigned to themselves (but two employees may be assigned to each other). Formally, all $$$b_i$$$ must be distinct integers between $$$1$$$ and $$$n$$$, and for any $$$i$$$, $$$b_i \ne i$$$ must hold.

The assignment is usually generated randomly. This year, as an experiment, all event participants have been asked who they wish to make a gift to. Each employee $$$i$$$ has said that they wish to make a gift to employee $$$a_i$$$.

Find a valid assignment $$$b$$$ that maximizes the number of fulfilled wishes of the employees.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.

Each test case consists of two lines. The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of participants of the event.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$; $$$a_i \ne i$$$) — wishes of the employees in order from $$$1$$$ to $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print two lines.

In the first line, print a single integer $$$k$$$ ($$$0 \le k \le n$$$) — the number of fulfilled wishes in your assignment.

In the second line, print $$$n$$$ distinct integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$; $$$b_i \ne i$$$) — the numbers of employees assigned to employees $$$1, 2, \ldots, n$$$.

$$$k$$$ must be equal to the number of values of $$$i$$$ such that $$$a_i = b_i$$$, and must be as large as possible. If there are multiple answers, print any.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, two valid assignments exist: $$$[3, 1, 2]$$$ and $$$[2, 3, 1]$$$. The former assignment fulfills two wishes, while the latter assignment fulfills only one. Therefore, $$$k = 2$$$, and the only correct answer is $$$[3, 1, 2]$$$.

Example input:
2
3
2 1 2
7
6 4 6 2 4 5 6

Example output:
2
3 1 2
4
6 4 7 2 3 5 1

Editorial:
Let $$$m$$$ be the number of different values among $$$a_i$$$ (that is, the number of distinct employees someone wishes to make a gift to).
It's easy to see that the answer, $$$k$$$, can not exceed $$$m$$$: each employee mentioned in $$$a_i$$$ allows us to fulfill at most one wish.
It turns out that $$$k$$$ can always be equal to $$$m$$$, and here's how.
We can visualize the problem in terms of graphs. We are given a functional graph $$$G$$$ (for each $$$i$$$, there is an edge from $$$i$$$ to $$$a_i$$$), and we need to find a directed graph that consists of cycles of length at least $$$2$$$ and shares as many edges with $$$G$$$ as possible.
For each vertex in $$$G$$$ that has at least one incoming edge, keep any of these edges and remove the others. Now every vertex has outdegree at most $$$1$$$ and indegree at most $$$1$$$. Hence, our graph becomes a collection of paths and cycles (isolated vertices are considered to be paths of length $$$0$$$).
Let the paths be $$$P_1, P_2, \ldots, P_t$$$. For each $$$i = 1 \ldots t$$$, create an edge from the end of path $$$P_i$$$ to the beginning of path $$$P_{i \bmod t + 1}$$$. That is, we are forming a single loop out of all the paths.
This will always work except for one case: if the new loop we are forming has length $$$1$$$. It means that we have a single isolated vertex $$$v$$$, and all other vertices form valid cycles.
If we ever arrive at this case, we can pick the initial edge going from $$$v$$$ to $$$a_v$$$, return it to the graph, and remove the other edge going from some vertex $$$u$$$ into $$$a_v$$$ that we kept. This will break the cycle containing vertex $$$a_v$$$ without changing the number of edges shared with the initial graph. Finally, add an edge from $$$u$$$ to $$$v$$$ closing the cycle, and that will give us a correct answer.
Alternatively, to not ever arrive at the bad case, we can use the knowledge of our future selves at the earlier stage of choosing the edges to keep and remove, and prioritize keeping edges going from vertices with indegree $$$0$$$.
Finally, randomized solutions are also possible. For example, we can select the edges to keep at random, write down the sets of vertices with indegree $$$0$$$ and vertices with outdegree $$$0$$$, shuffle both sets, and try to create an edge from the $$$i$$$-th vertex of one set to the $$$i$$$-th vertex of the other one. If we fail, and that can only happen when we try to create an edge from a vertex to self, we just start the process from scratch. With an argument similar to counting derangements, it can be shown that the expected number of iterations until we find a correct answer is constant.