/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
1,2,\dots,N の番号が付いた N 人の人がいます。
この N 人は全員同じゲームをしています。このゲームは 2 人で対戦するゲームです。N 人の人の実力は全て異なり、ゲームを行ったとき、実力が高い人が必ず勝ちます。
M 回ゲームを行いました。i 回目のゲームは人 A_i と B_i で行い、人 A_i が勝ちました。
N 人をゲームの実力が強い順に並べた列としてあり得る列のうち、辞書順最小のものを出力してください。
制約
- 2 \le N \le 2 \times 10^5
- 0 \le M \le 2 \times 10^5
- 1 \le A_i,B_i \le N
- A_i \neq B_i
- 入力は全て整数である。
- M 個の条件は矛盾しない。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
N 人をゲームの実力が強い順に並べた列としてあり得る列のうち、辞書順最小のものを空白区切りで出力せよ。
入力例 1
3 1 3 1
出力例 1
2 3 1
N 人のゲームの実力が強い順に並べた列として条件を満たす列は (2,3,1),(3,1,2),(3,2,1) です。このうち辞書順最小である (2,3,1) が答えとなります。
入力例 2
7 0
出力例 2
1 2 3 4 5 6 7
Problem Statement
There are N players numbered 1,2,\dots, and N.
These N players are playing the same game. In this game, two players play a match against each other. The N players have distinct strengths; the player with the greater strength always wins a match.
There were M matches. The i-th match was between players A_i and B_i, and player A_i won.
Find the lexicographically smallest possible sequence of the N players sorted by their strengths in descending order.
Constraints
- 2 \le N \le 2 \times 10^5
- 0 \le M \le 2 \times 10^5
- 1 \le A_i,B_i \le N
- A_i \neq B_i
- All values in the input are integers.
- The M conditions are consistent.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
Output
Find the lexicographically smallest possible sequence of the N players sorted by their strengths in descending order, separated by spaces.
Sample Input 1
3 1 3 1
Sample Output 1
2 3 1
(2,3,1), (3,1,2), and (3,2,1) are the possible sequences of the N players sorted by their strengths in descending order that satisfy the conditions. The answer is (2,3,1), which is the lexicographically smallest one among them.
Sample Input 2
7 0
Sample Output 2
1 2 3 4 5 6 7