← 返回题目列表

Codeforces · 1787/F

F. 逆变换

中文机器翻译题面 查看原题

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

排列是从 $$$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$$$

您在第 $$$k$$$ 天得到了排列 $$$a'$$$。

定义 $$$\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”。

示例

输入 #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

输出 #1

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$$$-th日)。此外,在满足该条件的所有排列中,它具有最小 $$$\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$$$。