日本情報オリンピック 第5回 女性部門

2025年2月8日
情報オリンピック日本委員会

問題文

カワウソのウソ太郎は新聞記者であり，近くで開かれる大規模なマラソン大会を取材している．

大会には N 人の選手が参加しており，選手には 1 から N までの番号が付けられている．ウソ太郎はこの大会の取材で，以下の情報をメモに記録した．

• 大会の開始時点において，N 人の選手は 1 位から N 位までのいずれかの順位であり，それらは互いに相異なっていた．
• 順位変動はちょうど M 回発生した．i 回目 (1 ≦ i ≦ M) の順位変動では，選手 A_i と選手 B_i の順位が入れ替わった．いずれの順位変動においても，入れ替わる 2 人の順位の差の絶対値は 1 であった．
• 複数の順位変動が同時に発生することはなかった．

ウソ太郎は，各選手の最終的な順位を表す順位表を新聞に載せたい．順位表は長さ N の数列であり，j 番目 (1 ≦ j ≦ N) の値は最終的に j 位になった選手の番号である．

しかしウソ太郎は，順位表を記録していなかったどころか，各順位変動でどちらが順位を上げた側であったかも記録していなかった．そこでウソ太郎は，メモの情報に矛盾しないような順位表のうち，辞書順で最小のものを選んで報告することにした．

数列 (a₁, a₂, …, a_N) が数列 (b₁, b₂, …, b_N) よりも辞書順で小さいとは，ある整数 k (1 ≦ k ≦ N) が存在し，以下の条件をともに満たすことをいう．

• 整数 l (1 ≦ l ≦ k-1) に対し a_l = b_l．
• a_k ＜ b_k．

選手の人数 N，およびメモに記録された各順位変動の情報が与えられたとき，メモの情報に矛盾しないような順位表が存在するか判定し，もし存在する場合はそのうち辞書順で最小のものを出力するプログラムを作成せよ．

制約

• 2 ≦ N ≦ 500 000．
• 1 ≦ M ≦ 500 000．
• 1 ≦ A_i ＜ B_i ≦ N (1 ≦ i ≦ M)．
• 入力される値はすべて整数である．

小課題

1. (13 点) N ≦ 8，M ≦ 8．
2. (16 点) A₁, A₂, …, A_M, B₁, B₂, …, B_M は相異なる．
3. (29 点) N ≦ 1 000，M ≦ 1 000．
4. (23 点) i 回目 (2 ≦ i ≦ M) の順位変動において，A_i と B_i のうち少なくとも片方は A₁, A₂, …, A_i-1, B₁, B₂, …, B_i-1 の中に現れない値である．
5. (19 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N M
A₁ B₁
A₂ B₂
︙
A_M B_M

出力

メモの情報に矛盾しないような順位表が存在しない場合，1 行で No と出力せよ．

メモの情報に矛盾しないような順位表が存在する場合，そのうち辞書順で最小のものを以下の形式で N+1 行で出力せよ．

• 1 行目には Yes を出力せよ．
• 1+j 行目 (1 ≦ j ≦ 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 の制約を満たす．