← 返回题目列表

AtCoder · agc060_e

E. 循环数

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

分数: 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.