F. Обратное преобразование
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ученый-перестановщик изучает самопреобразующуюся перестановку $$$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)}$$$ принимает минимально возможное значение.

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$) — длина $$$a$$$ и последний день.

Вторая строка содержит $$$n$$$ целых чисел $$$a'_1,a'_2,\ldots,a'_n$$$ ($$$1 \le a'_i \le n$$$) — перестановка в $$$k$$$-й день.

Гарантируется, что сумма $$$n$$$ не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных, если хотя бы одна перестановка $$$a$$$, из которой получается $$$a'$$$, существует, выведите «YES», и в следующей строке выведите $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ — начальную перестановку с минимальной суммой $$$\sum\limits^n_{i=1} \dfrac{1}{f(i)}$$$. Если ответов с минимальной суммой несколько, выведите любой.

Если нет ни одной подходящей перестановки, выведите «NO».

Пример
Входные данные
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
Примечание

Во втором наборе входных данных начальная перестановка может быть равна $$$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$$$.