分数: 1400 点
问题陈述
在这个问题中,排列 (1,2,\cdots,N) 有时被称为排列。
对于排列 a=(a_1,a_2,\cdots,a_N),让 f(a) 是循环数 a。 更准确地说,价值 f(a) 定义如下。
- 考虑一个由以下组成的无向图 N 顶点编号 1 to 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 测试用例。
约束
- 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.
- 输入中的所有数字均为整数。
输入
输入由标准输入按以下格式给出:
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 or No 可以是大写或小写。
如果存在多个解决方案,则其中任何一个都将被接受。
样本输入 1
3 3 3 1 3 2 2 2 2 1 4 8 1 2 3 4
示例输出 1
Yes 2 1 3 No Yes 1 2 3 4
在第一种情况下,让 x=(2,1,3) 使 y=(3,1,2),满意 f(x)+f(y)=2+1=3.