← 返回题目列表

AtCoder · joig2025_d

D. 最差记者 5

中文机器翻译题面 查看原题

配点: 100 点

問題文

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

在比赛中 N 玩家正在参加,并且玩家已经 它们的编号最大为 1 当编号达到 N 。乌太郎在报道这场比赛时在备忘录中记录了以下信息。

  • 比赛开始时,N 玩家是 来自 1 从等级 N 之前的任何等级,并且它们彼此不同。
  • 排名变化只是 发生 M 次。 在i 回目 (1 \leqq i \leqq M)的排名变化中,玩家 A_i 和玩家 B_i 的排名已交换。在任何排名变化中, 2 人物排名差异的绝对值为 这是 1 。
  • 多个排名变化没有同时发生。

乌太郎代表每位选手的最终排名。 我想在报纸上发表順位表。积分榜很长 是 N 的序列,j 番目 (1 \leqq j \leqq N) 的值最终是 j 这是获得第一名的玩家的号码。

然而,乌太郎不仅没有记录积分榜,也没有记录每次排名变化是哪一方上升。因此,乌太郎决定在与备忘录中的信息不矛盾的排名中选择并报告字典顺序最小的排名表。

数列 (a_1, a_2, \dots, a_N) 是一个序列 (b_1, b_2, \dots, b_N) 比按字典顺序最小是一个整数 k (1 \leqq k \leqq N) 存在并且满足以下两个条件。

  • 整数 l (1 \leqq l \leqq k-1)对于 a_l = b_l.
  • a_k < b_k.

玩家数量 给定 N和备忘录中记录的每次排名变化的信息,判断是否存在与备忘录中的信息不矛盾的排名表,如果存在,则编写一个程序,输出按字典顺序排列的最小的排名表。

制約

  • 2 \leqq N \leqq 500\,000.
  • 1 \leqq M \leqq 500\,000.
  • 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M).
  • 所有输入值均为整数。

小課題

  1. (13 点) N \leqq 8,M \leqq 8.
  2. (16 点) A_1, A_2, \dots, A_M, B_1, B_2, \dots, B_M 是不同的。
  3. (29 点) N \leqq 1\,000,M \leqq 1\,000.
  4. (23 点) i 回目 (2 \leqq i \leqq M的排名变化中, 至少A_i 和 将其放在 B_i 之一 该值未出现在 A_1, A_2, \dots, A_{i-1}, B_1, B_2, \dots, B_{i-1} 中。
  5. (19 点)没有额外的限制。

入力

输入按以下格式给出。 打印

N M 
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

如果没有与备忘录中的信息不矛盾的排名表, 在行1 中 输出 No 。

如果存在与备忘录中的信息不矛盾的排名表,请按以下格式选择最小的词典排名表。 N+1 行。

  • 1 在线 Yes 。
  • 1+j 行目 (1 \leqq j \leqq N)终于有了 j 打印排名第一的玩家的号码。

入力例 1

5 5
1 2
4 5
3 4
3 5
1 4

出力例 1

Yes
2
4
1
5
3

比赛开始时,按排名排列的玩家人数为 1 按排名顺序 假设 (1,2,3,5,4) 。

此时, 随着5 排名的变化,排名变化如下。

  1. 1 在排名变化时,1 排名玩家 1 和 将其放在 2 排名玩家 2 被替换。紧接着,每个等级的玩家编号为 1 按排名顺序 假设 (2,1,3,5,4) 。
  2. 2 在排名变化时,5 排名玩家 4 和 将其放在 4 排名玩家 5 被替换。紧接着,每个等级的玩家编号为 1 按排名顺序 假设 (2,1,3,4,5) 。
  3. 3 在排名变化时,3 排名玩家 3 和 将其放在 4 排名玩家 4 被替换。紧接着,每个等级的玩家编号为 1 按排名顺序 假设 (2,1,4,3,5) 。
  4. 4 在排名变化时,4 排名玩家 3 和 将其放在 5 排名玩家 5 被替换。紧接着,每个等级的玩家编号为 1 按排名顺序 假设 (2,1,4,5,3) 。
  5. 5 在排名变化时,2 排名玩家 1 和 将其放在 3 排名玩家 4 被替换。紧接着,每个等级的玩家编号为 1 按排名顺序 假设 (2,4,1,5,3) 。

因此,最终排名为 (2,4,1,5,3) 变为。

在与备忘录中的信息不矛盾的排名中, 按字典顺序,没有什么比(2,4,1,5,3) 小。因此,(2,4,1,5,3) 。

此输入示例是一个小作业。 1, 3, 5 满足约束。


入力例 2

3 4
1 3
2 3
1 3
2 3

出力例 2

No

没有任何排名表与备忘录中的信息不矛盾。

此输入示例是一个小作业。 1, 3, 5 满足约束。


入力例 3

8 3
1 8
3 5
4 7

出力例 3

Yes
1
8
2
3
5
4
7
6

此输入示例满足所有子任务约束。


入力例 4

6 5
1 2
1 3
1 4
1 5
1 6

出力例 4

Yes
1
6
5
4
3
2

此输入示例是一个小作业。 1, 3, 4, 5 满足约束。