CF1530D Secret Santa

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.

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 $ .

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.

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] $ .