CF1787F.Inverse Transformation

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$

For example, consider permutation $a = [2,3,1]$. On the first day, it becomes $[3,1,2]$. On the second day, it becomes $[2,3,1]$.

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.

一位排列科学家正在研究一个自变换排列 $a$，它由 $n$ 个元素 $a_1,a_2,\ldots,a_n$ 构成。

排列是指一个长度为 $n$、由 $1$ 到 $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]$。

你被给定第 $k$ 天的排列 $a'$。

定义 $\sigma(x) = a_x$，并定义 $f(x)$ 为满足 $\sigma^m(x) = x$ 的最小正整数 $m$，其中 $\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)}$ 达到可能的最小值。

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$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

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".

对于每个测试用例，若存在至少一个与给定的 $a'$ 一致的初始 $a$，则输出 "YES"，然后输出 $n$ 个整数 $a_1,a_2,\ldots,a_n$ —— 即满足条件且和 $\sum\limits^n_{i=1} \dfrac{1}{f(i)}$ 最小的初始排列。若存在多个具有最小和的解，输出任意一个即可。

若不存在合法排列，则输出 "NO"。

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$.

在第二个测试用例中，初始排列可以是 $a = [6,2,5,7,1,3,4]$，它在第一天变为 $[3,2,1,4,6,5,7]$，在第二天（即第 $k$ 天）变为 $a' = [1,2,3,4,5,6,7]$。此外，在所有满足条件的排列中，该排列使得 $\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$。