#P11726. [JOIG 2025] 最悪の記者 5 / Worst Reporter 5

[JOIG 2025] 最悪の記者 5 / Worst Reporter 5

题目背景

水獭乌苏太郎是一名报社记者,正在报道附近举行的一场大型马拉松比赛。

题目描述

共有 NN 名运动员参加比赛,编号从 11NN 。乌苏太郎在报道比赛时,在笔记中记录了如下信息:

  • 比赛开始时,NN 名运动员位于不同的位置上;
  • 比赛过程中,排名变化恰好发生了 MM 次:在第 i(1iM)i(1\le i\le M) 次排名变化中,运动员 AiA_iBiB_i 交换位置,保证排名变化前两位运动员之间没有其他运动员;
  • 没有两个排名变化同时发生。

乌苏太郎想在报纸上刊登一张排名表,表示比赛结束后运动员的排名:排名表是一个长度为 NN 的序列 PP,其中 PjP_j 代表排名为 jj 的运动员的编号。

然而乌苏太郎并没有记录排名表,也没有记录每次排名变化时哪一方的排名上升(即不知道是 AiA_i 超过了 BiB_i 还是反之)。于是他想让你判断是否存在一个排名表,使得不与他记录的信息矛盾;如果存在,他想让你求出字典序最小的排名表。

称一个长度为 NN 的排名表序列 aa 在字典序上小于另一个长度为 NN 的排名表序列 bb,当且仅当存在一个 k(1kN)k(1\le k\le N) 满足如下条件:

  • al=bl(1lk1)a_l=b_l(1\le l\le k-1)
  • ak<bka_k<b_k

输入格式

第一行输入两个整数 N,MN,M

接下来 MM 行,每行输入两个整数 Ai,BiA_i,B_i

输出格式

如果不存在满足条件的排名表,输出一行一个字符串 No

如果存在满足条件的排名表:

  • 第一行输出一个字符串 Yes
  • j+1(1jN)j+1(1\le j\le N) 行输出一个整数 PjP_j,其中 PP 表示满足条件且字典序最小的排名表。
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】

假设比赛开始时,运动员排名为 1,2,3,5,41,2,3,5,4

比赛过程如下:

  • 在第 11 次排名变化中,运动员 1,21,2 交换位置,排名变为 2,1,3,5,42,1,3,5,4
  • 在第 22 次排名变化中,运动员 4,54,5 交换位置,排名变为 2,1,3,4,52,1,3,4,5
  • 在第 33 次排名变化中,运动员 3,43,4 交换位置,排名变为 2,1,4,3,52,1,4,3,5
  • 在第 44 次排名变化中,运动员 3,53,5 交换位置,排名变为 2,1,4,5,32,1,4,5,3
  • 在第 55 次排名变化中,运动员 1,41,4 交换位置,排名变为 2,4,1,5,32,4,1,5,3

最终的排名表 P={2,4,1,5,3}P=\{2,4,1,5,3\}。可以证明这是字典序最小的。

该样例满足子任务 1,3,51,3,5 的限制。

【样例解释 #2】

不存在与给定信息不矛盾的排名表。

该样例满足子任务 1,3,51,3,5 的限制。

【样例解释 #3】

该样例满足所有子任务的限制。

【样例解释 #4】

该样例满足子任务 1,3,4,51,3,4,5 的限制。

【数据范围】

  • 2N5×1052\le N\le 5\times 10^5
  • 1M5×1051\le M\le 5\times 10^5
  • 1Ai<BiN(1iM)1\le A_i<B_i\le N(1\le i\le M)

【子任务】

  1. 1313 分)N,M8N,M\le 8
  2. 1616 分)A1,A2,,AM,B1,B2,,BMA_1,A_2,\ldots,A_M,B_1,B_2,\ldots,B_M 两两不同;
  3. 2929 分)N,M1000N,M\le 1000
  4. 2323 分)在第 i(2iM)i(2\le i\le M) 次排名变化中,AiA_iBiB_i 中至少有一个值在 A1,A2,,Ai1,B1,B2,,Bi1A_1,A_2,\ldots,A_{i-1},B_1,B_2,\ldots,B_{i-1} 中没有出现;
  5. 1919 分)无附加限制。