IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
781 . 早安美資程的闖關遊戲
TopCoder
Tags
Description
你聽你的同學說他前陣子參加了7/19-7/24的2022臺大資訊營《早安美資程》，並玩了有趣的RPG闖關遊戲。他說起了之前玩遊戲的故事：
「
我們那套遊戲有 $N$ 道關卡，比賽的規則就是看哪個小隊先解完所有 $N$ 道關卡。只要完成第 $i$ 關，就會獲得 $i$ 號道具──這些道具是用來解鎖更多關卡用的。
瞭解這個遊戲架構後，大關主在遊戲開始前給我們每個小隊一張通關祕笈，祕笈上有 $M + 1$ 條規則，前 $M$ 條規則每條的格式都是『必須要有道具 $a$ 才能解鎖關卡 $b$ 』。
而最後一條（第 $M + 1$ 條規則）寫著：『除了上述的 $M$ 條規則以外，沒有其他能阻止你們解鎖關卡的障礙了... 去闖吧！』
我們那隊太興奮地去闖關了所以幾乎沒有讀那個複雜的祕笈。因為這樣，我們常常跑個大老遠卻到了還沒解鎖的關卡，於是往前追溯需要的道具又發現能拿那個道具的關卡根本也還沒解鎖，總之我們就這樣玩得亂七八糟的 QQ
」
「如果能重來一遍呢？你會怎麼做？」你問道。
「呃...」他沉默了一陣子。
「要不要寫成表格？」
他莞爾一笑，「我寫歌。」
Input Format
第一行會包含兩個以空白分隔的正整數 $N, M$，代表關卡的數量和規則的數量。
接下來 $M$ 行都會是兩個以空白分隔的正整數 $a_i, b_i$，代表第 $i$ 條規則的具體內容是「必須要有道具 $a_i$ 才能解鎖關卡 $b_i$」。
- $1 \leq N \leq 10^ 5$
- $1 \leq M \leq 2 \cdot 10^ 5$
- $1 \leq a_i, b_i \leq N, \forall i = 1, 2, \ldots, N$
Output Format
他講完好冷的笑話之後，你提議可以寫好一個計畫好的闖關順序，只要按照這個順序闖關，就可以完成所有 $N$ 道關卡且不會在任何一個關卡吃閉門羹。
如果這個計畫是可行的，請在第一行輸出POSSIBLE；反之，請在第一行輸出IMPOSSIBLE。
如果這個計畫是可行的，請在第二行具體提出一種順序：輸出 $N$ 個以空白分隔的正整數 $p_1, p_2, \ldots, p_N$ ，代表只要先闖第 $p_1$ 關、接著闖第 $p_2$ 關、...、最後闖第 $p_N$ 關，便可以過程不碰壁地完成所有 $N$ 道關卡。
Sample Input 1
1 2
3 1
4 5
Sample Output 1
3 4 1 5 2
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~15 | 無額外限制 | 100 |