#P11726. [JOIG 2025] 最悪の記者 5 / Worst Reporter 5
[JOIG 2025] 最悪の記者 5 / Worst Reporter 5
题目背景
水獭乌苏太郎是一名报社记者,正在报道附近举行的一场大型马拉松比赛。
题目描述
共有 名运动员参加比赛,编号从 到 。乌苏太郎在报道比赛时,在笔记中记录了如下信息:
- 比赛开始时, 名运动员位于不同的位置上;
- 比赛过程中,排名变化恰好发生了 次:在第 次排名变化中,运动员 和 交换位置,保证排名变化前两位运动员之间没有其他运动员;
- 没有两个排名变化同时发生。
乌苏太郎想在报纸上刊登一张排名表,表示比赛结束后运动员的排名:排名表是一个长度为 的序列 ,其中 代表排名为 的运动员的编号。
然而乌苏太郎并没有记录排名表,也没有记录每次排名变化时哪一方的排名上升(即不知道是 超过了 还是反之)。于是他想让你判断是否存在一个排名表,使得不与他记录的信息矛盾;如果存在,他想让你求出字典序最小的排名表。
称一个长度为 的排名表序列 在字典序上小于另一个长度为 的排名表序列 ,当且仅当存在一个 满足如下条件:
- ;
- 。
输入格式
第一行输入两个整数 。
接下来 行,每行输入两个整数 。
输出格式
如果不存在满足条件的排名表,输出一行一个字符串 No
。
如果存在满足条件的排名表:
- 第一行输出一个字符串
Yes
; - 第 行输出一个整数 ,其中 表示满足条件且字典序最小的排名表。
5 5
1 2
4 5
3 4
3 5
1 4
Yes
2
4
1
5
3
3 4
1 3
2 3
1 3
2 3
No
8 3
1 8
3 5
4 7
Yes
1
8
2
3
5
4
7
6
6 5
1 2
1 3
1 4
1 5
1 6
Yes
1
6
5
4
3
2
提示
【样例解释 #1】
假设比赛开始时,运动员排名为 。
比赛过程如下:
- 在第 次排名变化中,运动员 交换位置,排名变为 ;
- 在第 次排名变化中,运动员 交换位置,排名变为 ;
- 在第 次排名变化中,运动员 交换位置,排名变为 ;
- 在第 次排名变化中,运动员 交换位置,排名变为 ;
- 在第 次排名变化中,运动员 交换位置,排名变为 ;
最终的排名表 。可以证明这是字典序最小的。
该样例满足子任务 的限制。
【样例解释 #2】
不存在与给定信息不矛盾的排名表。
该样例满足子任务 的限制。
【样例解释 #3】
该样例满足所有子任务的限制。
【样例解释 #4】
该样例满足子任务 的限制。
【数据范围】
- ;
- ;
- 。
【子任务】
- ( 分);
- ( 分) 两两不同;
- ( 分);
- ( 分)在第 次排名变化中, 和 中至少有一个值在 中没有出现;
- ( 分)无附加限制。