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 翻译