D. Секретный Санта
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В компании ВКонтакте в декабре традиционно проводится мероприятие под названием «Секретный Санта». Суть его в следующем.

В мероприятии участвуют $$$n$$$ сотрудников, пронумерованных от $$$1$$$ до $$$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$$$, и должно быть максимальным возможным. Если существует несколько решений, выведите любое из них.

Пример
Входные данные
2
3
2 1 2
7
6 4 6 2 4 5 6
Выходные данные
2
3 1 2
4
6 4 7 2 3 5 1
Примечание

В первом наборе входных данных существует два корректных назначения — $$$[3, 1, 2]$$$ и $$$[2, 3, 1]$$$. В первом случае будет выполнено два пожелания, а во втором — одно. Таким образом, $$$k = 2$$$, и верным ответом является только назначение $$$[3, 1, 2]$$$.