AT_joig2025_d 最悪の記者 5 (Worst Reporter 5)

カワウソのウソ太郎は新聞記者であり，近くで開かれる大規模なマラソン大会を取材している． 大会には $ 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 $ ，およびメモに記録された各順位変動の情報が与えられたとき，メモの情報に矛盾しないような順位表が存在するか判定し，もし存在する場合はそのうち辞書順で最小のものを出力するプログラムを作成せよ．

入力は以下の形式で与えられる． > $ 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. ( $ 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 $ 点) 追加の制約はない． ### Sample Explanation 1 大会の開始時点において，順位ごとの選手の番号は $ 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 $ の制約を満たす． ### Sample Explanation 2 メモの情報に矛盾しないような順位表は存在しない． この入力例は小課題 $ 1, 3, 5 $ の制約を満たす． ### Sample Explanation 3 この入力例はすべての小課題の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 1, 3, 4, 5 $ の制約を満たす． ### Constraints - $ 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 $ )． - 入力される値はすべて整数である．