В компании ВКонтакте в декабре традиционно проводится мероприятие под названием «Секретный Санта». Суть его в следующем.
В мероприятии участвуют \(n\) сотрудников, пронумерованных от \(1\) до \(n\). Каждому сотруднику \(i\) назначается другой сотрудник \(b_i\), которому сотрудник \(i\) должен сделать новогодний подарок. При этом каждый сотрудник назначается ровно одному другому сотруднику, и никто не назначается сам себе (но возможно, что два сотрудника окажутся назначены друг другу). Формально, все \(b_i\) должны быть различными целыми числами от \(1\) до \(n\), и для любого \(i\) должно выполняться \(b_i \ne i\).
Как правило, назначение происходит случайным образом. Но в качестве эксперимента у участников мероприятия спросили, кому бы они хотели сделать подарок. Каждый сотрудник \(i\) сказал, что желает сделать подарок сотруднику \(a_i\).
Найдите такое корректное назначение \(b\), что как можно больше пожеланий сотрудников окажется выполнено.
Выходные данные
Для каждого набора входных данных выведите две строки.
В первой строке выведите целое число \(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\), и должно быть максимальным возможным. Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных существует два корректных назначения — \([3, 1, 2]\) и \([2, 3, 1]\). В первом случае будет выполнено два пожелания, а во втором — одно. Таким образом, \(k = 2\), и верным ответом является только назначение \([3, 1, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|