Ученый-перестановщик изучает самопреобразующуюся перестановку \(a\), состоящую из \(n\) элементов \(a_1,a_2,\ldots,a_n\).
Перестановка — это последовательность целых чисел от \(1\) до \(n\) длины \(n\), содержащая каждое число ровно один раз. Например, \([1]\), \([4, 3, 5, 1, 2]\) являются перестановками, а \([1, 1]\), \([4, 3, 1]\) — нет.
Перестановка изменяется каждый день. Каждый день каждый элемент \(x\) заменяется на \(a_x\), то есть \(a_x\) станет \(a_{a_x}\). Другими словами,
- в первый день перестановка примет вид \(b\), где \(b_x = a_{a_x}\);
- на второй день перестановка примет вид \(c\), где \(c_x = b_{b_x}\);
- \(\ldots\)
Например, рассмотрим перестановку
\(a = [2,3,1]\). В первый день она станет равна
\([3,1,2]\). На второй день она станет равна
\([2,3,1]\).
Вам дана перестановка \(a'\) на \(k\)-й день.
Определим \(\sigma(x) = a_x\) и определим \(f(x)\) как минимальное натуральное число \(m\) такое, что \(\sigma^m(x) = x\), где \(\sigma^m(x)\) обозначает \(\underbrace{\sigma(\sigma(\ldots \sigma}_{m \text{ раз}}(x) \ldots))\).
Например, если \(a = [2,3,1]\), то \(\sigma(1) = 2\), \(\sigma^2(1) = \sigma(\sigma(1)) = \sigma(2) = 3\), \(\sigma^3(1) = \sigma(\sigma(\sigma(1))) = \sigma(3) = 1\), поэтому \(f(1) = 3\). И если \(a=[4,2,1,3]\), то \(\sigma(2) = 2\), значит, \(f(2) = 1\); \(\sigma(3) = 1\), \(\sigma^2(3) = 4\), \(\sigma^3(3) = 3\), поэтому \(f(3) = 3\).
Найдите начальную перестановку \(a\) такую, что \(\sum\limits^n_{i=1} \dfrac{1}{f(i)}\) принимает минимально возможное значение.
Выходные данные
Для каждого набора входных данных, если хотя бы одна перестановка \(a\), из которой получается \(a'\), существует, выведите «YES», и в следующей строке выведите \(n\) целых чисел \(a_1,a_2,\ldots,a_n\) — начальную перестановку с минимальной суммой \(\sum\limits^n_{i=1} \dfrac{1}{f(i)}\). Если ответов с минимальной суммой несколько, выведите любой.
Если нет ни одной подходящей перестановки, выведите «NO».
Примечание
Во втором наборе входных данных начальная перестановка может быть равна \(a = [6,2,5,7,1,3,4]\), которая станет \([3,2,1,4,6,5,7]\) в первый день и \(a' = [1,2,3,4,5,6,7]\) во второй день (\(k\)-й день). Кроме того, среди всех перестановок, удовлетворяющих этому, она имеет минимальную \(\sum\limits^n_{i=1} \dfrac{1}{f(i)}\), которая равна \(\dfrac{1}{4}+\dfrac{1}{1}+\dfrac{1}{4}+\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{2}=3\).
В пятом наборе входных данных начальная перестановка может быть равна \(a = [4,2,1,3]\), которая станет \([3,2,4,1]\) в первый день, \([4,2,1,3]\) на второй день и так далее. Таким образом, в \(8\)-й день (\(k\)-й день) в итоге получится \(a' = [4,2,1,3]\). Для такой перестановки достигается минимальное значение \(\sum\limits^n_{i=1} \dfrac{1}{f(i)} = \dfrac{1}{3} + \dfrac{1}{1} + \dfrac{1}{3} + \dfrac{1}{3} = 2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
5 3
1 2 3 4 5
7 2
1 2 3 4 5 6 7
8 998
1 2 3 4 5 6 7 8
6 1
6 3 5 4 1 2
4 8
4 2 1 3
9 1
1 5 4 8 7 6 3 2 9
5 9999999
2 3 4 5 1
7 97843220
4 6 1 2 7 5 3
3 1000000000
2 1 3
12 3
8 9 10 1 5 3 11 4 7 6 12 2
|
YES
2 3 4 1 5
YES
6 2 5 7 1 3 4
YES
2 3 4 5 6 7 8 1
YES
3 1 6 4 2 5
YES
4 2 1 3
NO
YES
3 4 5 1 2
YES
2 5 4 6 3 7 1
NO
YES
3 7 8 6 5 1 12 10 11 4 2 9
|