E - Number of Cycles 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 1400 点

問題文

この問題では，順列と言った際には (1,2,\cdots,N) の順列を指すものとします．

順列 a=(a_1,a_2,\cdots,a_N) に対し，f(a) を a のサイクルの個数と定義します． より正確には，f(a) の値は次のように定義されます．

  • 1 から N までの番号のついた 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 である．

1 つの入力ファイルにつき，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) の順列
  • 1 つの入力ファイルにつき，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, 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

1 つめのケースでは，x=(2,1,3) とすれば y=(3,1,2) となり，f(x)+f(y)=2+1=3 となります．

Score : 1400 points

Problem Statement

In this problem, a permutation of (1,2,\cdots,N) is occasionally called just a permutation.

For a permutation a=(a_1,a_2,\cdots,a_N), let f(a) be the number of cycles in a. More accurately, the value of f(a) is defined as follows.

  • Consider an undirected graph consisting of N vertices numbered 1 to N. For each 1 \leq i \leq N, add an edge connecting vertex i and vertex a_i. Then, let f(a) be the number of connected components in this graph.

You are given a permutation P=(P_1,P_2,\cdots,P_N) and an integer K. Determine whether there is a permutation x that satisfies the following condition, and construct one if it exists.

  • Let y_i=P_{x_i} to define a permutation y.
  • Then, f(x)+f(y)=K holds.

For each input file, solve T test cases.

Constraints

  • 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) is a permutation of (1,2,\cdots,N).
  • In each input file, the sum of N does not exceed 2 \times 10^5.
  • All numbers in the input are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is in the following format:

N K
P_1 P_2 \cdots P_N

Output

For each case, if no permutation x satisfies the condition, print No. Otherwise, print your answer in the following format:

Yes
x_1 x_2 \cdots x_N

Each character in Yes or No in the output may be either uppercase or lowercase. If multiple solutions exist, any of them will be accepted.

Sample Input 1

3
3 3
1 3 2
2 2
2 1
4 8
1 2 3 4

Sample Output 1

Yes
2 1 3
No
Yes
1 2 3 4

In the first case, letting x=(2,1,3) makes y=(3,1,2), satisfying f(x)+f(y)=2+1=3.