一个 n 个元素的整数数组 A={a_i},a_i\in[1,n],你手上有一个整数 x\in [1,n],每次操作会把 x 变成 a_x。
容易发现,对于任意的 x 的初始值,通过操作(包括不操作)得到的数的个数是有限的,定义 b_i 表示当初始 x=i 的情况下,通过任意次操作可以得到的不同的数的集合大小。
比如当 A={2,1,3,3,4},那么他的 B 就是 {2,2,1,2,3}。
1 通过 0,1 次操作可以得到 1,2。
2 可以通过 0,1 次操作得到 2,1。
3 可以通过 0 次操作得到 3。
4 可以通过 0,1 次操作得到 4,3。
5 可以通过 0,1,2 次操作得到 5,4,3。
所以 B 是 {2,2,1,2,3}。
现在给定你 B={b_i},询问是否存在 A。如果存在,请给出一个构造。
你需要解决多组询问。
第一行一个整数 t,表示数据组数。
对于每组数据,有两行。
第一行一个整数 n。表示 B 数组中的数量。
第二行 n 个整数,第 i 个整数表示 b_i。
对于每组数据,第一行输出 Yes
或者 No
表示是否存在 A。
如果你的回答是 Yes
,则接下来第二行输出一行 n 个整数,表示 A。
如果你的回答是 No
,那么不应存在第二行。
1 5 2 2 1 2 3
Yes 2 1 3 3 4
2 1 1 2 2 2
Yes 1 Yes 2 1
2 5 5 2 3 4 1 10 5 2 2 5 2 2 5 5 6 5
Yes 4 5 2 3 5 Yes 10 3 2 1 6 5 4 7 1 8
subtask\ 1: 保证无解,5 分
subtask\ 2: 保证 b_i=1,5 分
subtask\ 3: 保证 b_i=i,5 分
subtask\ 4: 保证 b_i=2,5 分
subtask\ 5: 保证 b_i=n,5 分
subtask\ 6: 保证 \sum n\leq 3000,15 分
subtask\ 7: 保证 \sum n\leq 10000,20 分
subtask\ 8: 保证 t=1,20 分
subtask\ 9: 保证 \sum n\leq 200000,20 分
时间限制 | 1 秒 |
内存限制 | 512 MB |