Inverse Transformation
Contest: TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2500
Tags: constructive algorithms, implementation, math

A permutation scientist is studying a self-transforming permutation $$$a$$$ consisting of $$$n$$$ elements $$$a_1,a_2,\ldots,a_n$$$.

A permutation is a sequence of integers from $$$1$$$ to $$$n$$$ of length $$$n$$$ containing each number exactly once. For example, $$$[1]$$$, $$$[4, 3, 5, 1, 2]$$$ are permutations, while $$$[1, 1]$$$, $$$[4, 3, 1]$$$ are not.

The permutation transforms day by day. On each day, each element $$$x$$$ becomes $$$a_x$$$, that is, $$$a_x$$$ becomes $$$a_{a_x}$$$. Specifically:

- on the first day, the permutation becomes $$$b$$$, where $$$b_x = a_{a_x}$$$;
- on the second day, the permutation becomes $$$c$$$, where $$$c_x = b_{b_x}$$$;
- $$$\ldots$$$

You're given the permutation $$$a'$$$ on the $$$k$$$-th day.

Define $$$\sigma(x) = a_x$$$, and define $$$f(x)$$$ as the minimal positive integer $$$m$$$ such that $$$\sigma^m(x) = x$$$, where $$$\sigma^m(x)$$$ denotes $$$\underbrace{\sigma(\sigma(\ldots \sigma}_{m \text{ times}}(x) \ldots))$$$.

For example, if $$$a = [2,3,1]$$$, then $$$\sigma(1) = 2$$$, $$$\sigma^2(1) = \sigma(\sigma(1)) = \sigma(2) = 3$$$, $$$\sigma^3(1) = \sigma(\sigma(\sigma(1))) = \sigma(3) = 1$$$, so $$$f(1) = 3$$$. And if $$$a=[4,2,1,3]$$$, $$$\sigma(2) = 2$$$ so $$$f(2) = 1$$$; $$$\sigma(3) = 1$$$, $$$\sigma^2(3) = 4$$$, $$$\sigma^3(3) = 3$$$ so $$$f(3) = 3$$$.

Find the initial permutation $$$a$$$ such that $$$\sum\limits^n_{i=1} \dfrac{1}{f(i)}$$$ is minimum possible.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$) — the length of $$$a$$$, and the last day.

The second line contains $$$n$$$ integers $$$a'_1,a'_2,\ldots,a'_n$$$ ($$$1 \le a'_i \le n$$$) — the permutation on the $$$k$$$-th day.

It's guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, if at least one initial $$$a$$$ consistent with the given $$$a'$$$ exists, print "YES", then print $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ — the initial permutation with the smallest sum $$$\sum\limits^n_{i=1} \dfrac{1}{f(i)}$$$. If there are multiple answers with the smallest sum, print any.

If there are no valid permutations, print "NO".

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the second test case, the initial permutation can be $$$a = [6,2,5,7,1,3,4]$$$, which becomes $$$[3,2,1,4,6,5,7]$$$ on the first day and $$$a' = [1,2,3,4,5,6,7]$$$ on the second day (the $$$k$$$-th day). Also, among all the permutations satisfying that, it has the minimum $$$\sum\limits^n_{i=1} \dfrac{1}{f(i)}$$$, which is $$$\dfrac{1}{4}+\dfrac{1}{1}+\dfrac{1}{4}+\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{2}=3$$$.

In the fifth test case, the initial permutation can be $$$a = [4,2,1,3]$$$, which becomes $$$[3,2,4,1]$$$ on the first day, $$$[4,2,1,3]$$$ on the second day, and so on. So it finally becomes $$$a' = [4,2,1,3]$$$ on the $$$8$$$-th day (the $$$k$$$-th day). And it has the minimum $$$\sum\limits^n_{i=1} \dfrac{1}{f(i)} = \dfrac{1}{3} + \dfrac{1}{1} + \dfrac{1}{3} + \dfrac{1}{3} = 2$$$.

Example input:
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

Example output:
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

Editorial:
Consider another question: Given the initial permutation $$$a$$$ and find the permutation $$$a'$$$ on the $$$k$$$-th day?
After a day, element $$$x$$$ will become $$$\sigma(x) = a_x$$$, so we can consider the numbers as nodes, and we add directed edges from $$$x$$$ to $$$a_x$$$. Note that $$$a$$$ is a permutation, so the graph consists of several cycles. After one day, $$$a_x$$$ will become $$$a_{\sigma(x)} = a_{a_x}$$$ – the second element after $$$x$$$ in the corresponding cycle. Similarly, we can conclude that $$$a_x$$$ will become the $$$2^k$$$-th element after $$$x$$$.
If a cycle $$$c$$$ has an odd length $$$l$$$. Because $$$2^k \bmod l \neq 0$$$, the cycle will never split, the element $$$c_x$$$ will become $$$c_{(x+2^k)\bmod l}$$$ on the $$$k$$$-th day. Otherwise, if a cycle $$$c$$$ has an even length $$$l$$$, after the first day, $$$c_1$$$ will become $$$c_3$$$, $$$c_3$$$ will become $$$c_5$$$, $$$\ldots$$$, $$$c_{2l-1}$$$ will become $$$c_1$$$. And so will the even indices – that means the original cycle split into two small cycles of the same size $$$\dfrac{l}{2}$$$. So, if a cycle of length $$$l = p\cdots 2^q$$$ will split into $$$2^q$$$ small cycles of length $$$p$$$ after exactly $$$q$$$ days.
Because the length of a cycle $$$l\le n$$$, so we can perform the transformation for at least $$$\log n$$$ days to split all the cycles of even lengths into cycles of odd lengths. Then we can use our conclusion to calculate the final permutation on the $$$k$$$-th day.
Now let's back to our question. We observed that $$$\sum\limits^n_{i=1} \dfrac{1}{f(i)}$$$ means the number of cycles in the original graph. Then we need to construct the original permutation $$$a$$$ of the least possible cycle. As we've said before, the cycle of length $$$l = p\cdots 2^q$$$ will split into $$$2^q$$$ small cycles of length $$$p$$$ after exactly $$$q$$$ days. So we can count all the cycles in permutation $$$a'$$$.
For cycles of odd length $$$l$$$, we can combine some of them. Specifically, we can combine $$$2^q$$$ cycles into a cycle of length $$$l\cdots 2^q$$$ in the original permutation $$$a$$$. Note that $$$q$$$ must be less than or equal to $$$k$$$.
And for cycles of even length $$$l$$$, we can also combine them. But because they haven't been split on the $$$k$$$-th day, we must combine exactly $$$2^k$$$ cycles. So if the number of these cycles isn't a multiple of $$$2^k$$$, just print NO.