开始 2024-10-07 14:00:00

【2024CSP-J】模拟赛-2

结束 2024-10-07 17:30:00
Contest is over.
当前 2026-10-25 05:40:24

E. 【J】T5 小清新桂冠题

描述

一个 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 分


Submit

登录

注册
时间限制 1 秒
内存限制 512 MB
提交