AT_agc060_e.[AGC060E] Number of Cycles

在本题中，提到“顺序”时，指的是 $ (1,2,\cdots,N) $ 的一个排列。

对于一个排列 $ a=(a_1,a_2,\cdots,a_N) $，定义 $ f(a) $ 为 $ a $ 的循环节（cycle）的个数。更准确地说，$ f(a) $ 的值定义如下：

• 考虑一个有 $ N $ 个顶点、编号为 $ 1 $ 到 $ N $ 的无向图。对于每个 $ 1\leq i\leq N $，在顶点 $ i $ 和顶点 $ a_i $ 之间连一条边。此时，该图的连通分量个数即为 $ f(a) $。

给定一个排列 $ P=(P_1,P_2,\cdots,P_N) $ 和一个整数 $ K $。判断是否存在一个排列 $ x $，使得下列条件成立，并在存在时构造出一个解：

• 令 $ y_i=P_{x_i} $，从而得到排列 $ y $。
• 满足 $ f(x)+f(y)=K $。

对于每个输入文件，需要解答 $ T $ 个测试用例。

输入以如下格式从标准输入读入：

$ T $
$ case_1 $
$ case_2 $
$\vdots$
$ case_T $

每个测试用例的格式如下：

$ N $ $ K $ $ P_1 $ $ P_2 $ $ \cdots $ $ P_N $

对于每个测试用例，如果不存在满足条件的排列 $ x $，输出 No。如果存在，输出如下格式的答案：

Yes $ x_1 $ $ x_2 $ $ \cdots $ $ x_N $

输出 Yes 或 No 时，字母大小写均可。若存在多个解，输出任意一个均可。

数据范围

• $ 1\leq T\leq 10^5 $
• $ 2\leq N\leq 2\times 10^5 $
• $ 2\leq K\leq 2N $
• $ (P_1,P_2,\cdots,P_N) $ 是 $ (1,2,\cdots,N) $ 的一个排列
• 每个输入文件中所有 $ N $ 的总和不超过 $ 2\times 10^5 $
• 输入的所有数均为整数

样例解释 1

在第 $ 1 $ 个测试用例中，取 $ x=(2,1,3) $，则 $ y=(3,1,2) $，此时 $ f(x)+f(y)=2+1=3 $。

由 ChatGPT 4.1 翻译