a224. D. 賽馬播報 - YUTEH ZeroJudge

內容

2022 網際網路程式設計全國大賽國中組決賽

在 AT7 結束了程式競賽之旅後，沉迷於知名賽馬培育手機遊戲的他，決定投入賽馬運動，立志成為最強的練馬師，訓練出最強的馬匹！而身為專業競賽轉播員的慦乙己，播報賽馬當然也是難不倒他，他也將繼續支持 AT7，在 AT7 的練馬師之路上不斷給予最真誠的祝福。

在今天的賽馬比賽中，一共有 N 匹馬正在環狀的賽道上奔馳，所有的馬分別以 1 到 N 的正整數編號，且任兩匹馬的編號皆相異。在比賽開始時，所有馬匹會依照賽前決定的起跑順序 a₁,a₂,...,a_N依序從跑道上的起點出發，以順時針的方向繞行環狀賽道。在編號 a_N的馬出發之前，這段時間被視為「熱身時間」，此時不會有馬匹已經跑完一整圈回到起跑點，也不允許較晚出發的馬匹超越前方馬匹的狀況發生。

在賽馬比賽中，發生馬匹順序交換的「超車」狀況是最精彩的了！每次超車發生時，慦乙己便會大聲地播報：「編號 x 的馬超越了編號 y！」在賽道上，我們假設每匹馬的位置都是不一樣的，並且每匹馬都只會以順時針方向移動。因此當 x 超越 y 時，y 必須恰好是 x 順時針方向的下一匹馬，在超越過後，x 和 y 在賽道上的順序便會交換。

具體來說，從目前賽道上的任意一匹馬開始，以順時針方向依序記錄下 N 匹馬的編號為 h₁,h₂,...,h_N。對於所有 1 ≤ i < N，編號為 h_i的馬其順時針方向的下一匹馬為 h_i₊₁，在 h_i超越 h_i₊₁之後，所有馬匹的順序將變為 h₁,h₂,...,h_i₊₁,h_i,...,h_N。而對於編號 h_N的馬，其順時針方向的下一匹馬為 h₁，在 h_N超越 h₁後，所有馬匹的順序將變為 h_N,h₂,h₃,...,h_N−2,h_N−1,h₁。

精采刺激的比賽正在進行，慦乙己依序記錄下了這次比賽發生的 M 次超越事件，卻忘記了比賽開始前每匹馬的起跑順序！他想請你寫一支程式回推出可能的起跑順序，或告訴他他的記錄有誤，沒有起跑順序可以依序讓這 M 次超越發生。

以範例測資1為例，[1,3,2,4],[2,4,1,3],[3,2,4,1]等都是可能的起跑順序；而[1,2,3,4],[4,3,2,1] 等都不是可能的起跑順序。

輸入說明

輸入的第一行，包含兩個整數 N,M，表示馬的數量以及超越事件發生的次數。

接下來 M 行，每行包含兩個整數 x,y，表示依序發生的超越事件。

2 ≤ N ≤ 10⁵5
0 ≤ M ≤ 10
1 ≤ x,y ≤ N
x ̸= y

輸出說明

若不存在可能的起跑順序，請輸出一行No；否則，請先輸出一行Yes，第二行請輸出 N 個整數 a_i，表示起跑的順序。

如果有多種可能的順序，你可以輸出任意一種。

請注意，同一行兩個整數間請以一個空白隔開，並且最後一個整數後不得有空白。

範例輸入

4 2
2 3
1 4

範例輸出

Yes
1 3 2 4

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (1%): 1.0s , <1K
公開測資點#1 (1%): 1.0s , <1K
公開測資點#2 (1%): 1.0s , <1K
公開測資點#3 (1%): 1.0s , <1K
公開測資點#4 (1%): 1.0s , <1K
公開測資點#5 (1%): 1.0s , <1K
公開測資點#6 (1%): 1.0s , <1K
公開測資點#7 (1%): 1.0s , <1K
公開測資點#8 (1%): 1.0s , <1K
公開測資點#9 (1%): 1.0s , <1K
公開測資點#10 (1%): 1.0s , <1M
公開測資點#11 (1%): 1.0s , <1M
公開測資點#12 (1%): 1.0s , <1K
公開測資點#13 (1%): 1.0s , <1K
公開測資點#14 (1%): 1.0s , <1K
公開測資點#15 (1%): 1.0s , <1K
公開測資點#16 (1%): 1.0s , <1K
公開測資點#17 (1%): 1.0s , <1K
公開測資點#18 (1%): 1.0s , <1K
公開測資點#19 (1%): 1.0s , <1K
公開測資點#20 (1%): 1.0s , <1M
公開測資點#21 (1%): 1.0s , <1M
公開測資點#22 (1%): 1.0s , <1K
公開測資點#23 (1%): 1.0s , <1K
公開測資點#24 (1%): 1.0s , <1K
公開測資點#25 (1%): 1.0s , <1K
公開測資點#26 (1%): 1.0s , <1K
公開測資點#27 (1%): 1.0s , <1M
公開測資點#28 (1%): 1.0s , <1M
公開測資點#29 (1%): 1.0s , <1K
公開測資點#30 (1%): 1.0s , <1K
公開測資點#31 (1%): 1.0s , <1K
公開測資點#32 (1%): 1.0s , <1K
公開測資點#33 (1%): 1.0s , <1K
公開測資點#34 (1%): 1.0s , <1K
公開測資點#35 (1%): 1.0s , <1M
公開測資點#36 (1%): 1.0s , <1M
公開測資點#37 (1%): 1.0s , <1M
公開測資點#38 (1%): 1.0s , <1M
公開測資點#39 (1%): 1.0s , <1M
公開測資點#40 (1%): 1.0s , <1M
公開測資點#41 (1%): 1.0s , <1M
公開測資點#42 (1%): 1.0s , <1M
公開測資點#43 (1%): 1.0s , <1M
公開測資點#44 (1%): 1.0s , <1M
公開測資點#45 (1%): 1.0s , <1M
公開測資點#46 (1%): 1.0s , <1M
公開測資點#47 (1%): 1.0s , <1M
公開測資點#48 (1%): 1.0s , <1M
公開測資點#49 (1%): 1.0s , <1M
公開測資點#50 (1%): 1.0s , <1M
公開測資點#51 (1%): 1.0s , <1M
公開測資點#52 (1%): 1.0s , <1M
公開測資點#53 (1%): 1.0s , <1M
公開測資點#54 (1%): 1.0s , <1K
公開測資點#55 (1%): 1.0s , <1K
公開測資點#56 (1%): 1.0s , <1K
公開測資點#57 (1%): 1.0s , <1K
公開測資點#58 (1%): 1.0s , <1M
公開測資點#59 (1%): 1.0s , <1M
公開測資點#60 (1%): 1.0s , <1M
公開測資點#61 (1%): 1.0s , <1M
公開測資點#62 (1%): 1.0s , <1M
公開測資點#63 (1%): 1.0s , <1M
公開測資點#64 (1%): 1.0s , <1M
公開測資點#65 (1%): 1.0s , <1M
公開測資點#66 (1%): 1.0s , <1K
公開測資點#67 (1%): 1.0s , <1K
公開測資點#68 (1%): 1.0s , <1M
公開測資點#69 (1%): 1.0s , <1M
公開測資點#70 (1%): 1.0s , <1M
公開測資點#71 (1%): 1.0s , <1M
公開測資點#72 (1%): 1.0s , <1M
公開測資點#73 (1%): 1.0s , <1M
公開測資點#74 (1%): 1.0s , <1M
公開測資點#75 (1%): 1.0s , <1M
公開測資點#76 (1%): 1.0s , <1M
公開測資點#77 (1%): 1.0s , <1M
公開測資點#78 (1%): 1.0s , <1M
公開測資點#79 (1%): 1.0s , <1M
公開測資點#80 (1%): 1.0s , <1M
公開測資點#81 (1%): 1.0s , <1M
公開測資點#82 (1%): 1.0s , <10M
公開測資點#83 (1%): 1.0s , <10M
公開測資點#84 (1%): 1.0s , <10M
公開測資點#85 (1%): 1.0s , <10M
公開測資點#86 (1%): 1.0s , <10M
公開測資點#87 (1%): 1.0s , <10M
公開測資點#88 (1%): 1.0s , <10M
公開測資點#89 (1%): 1.0s , <10M
公開測資點#90 (1%): 1.0s , <10M
公開測資點#91 (1%): 1.0s , <10M
公開測資點#92 (1%): 1.0s , <10M
公開測資點#93 (1%): 1.0s , <1M
公開測資點#94 (1%): 1.0s , <1M
公開測資點#95 (1%): 1.0s , <1K
公開測資點#96 (1%): 1.0s , <1K
公開測資點#97 (1%): 1.0s , <1K
公開測資點#98 (2%): 1.0s , <1K

提示：

標籤:

2022國中組決賽

出處:

NPSC [管理者：

zero (管理員)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」