

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
(1, 2, \dots, N) を並び替えて得られる数列 P であって以下の条件を満たすもののうち、辞書順で最小のものを求めてください。
- i = 1, \dots, M に対し、P において A_i は B_i よりも先に現れる。
ただし、そのような P が存在しない場合は -1
と出力してください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq N
- A_i \neq B_i
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 \vdots A_M B_M
出力
答えを出力せよ。
入力例 1
4 3 2 1 3 4 2 4
出力例 1
2 1 3 4
条件を満たす P は (2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 2, 4, 1) の 5 つです。これらのうち辞書順で最小のものは (2, 1, 3, 4) です。
入力例 2
2 3 1 2 1 2 2 1
出力例 2
-1
条件を満たす P は存在しません。
Score : 400 points
Problem Statement
Among the sequences P that are permutations of (1, 2, \dots, N) and satisfy the condition below, find the lexicographically smallest sequence.
- For each i = 1, \dots, M, A_i appears earlier than B_i in P.
If there is no such P, print -1
.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq N
- A_i \neq B_i
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 \vdots A_M B_M
Output
Print the answer.
Sample Input 1
4 3 2 1 3 4 2 4
Sample Output 1
2 1 3 4
The following five permutations P satisfy the condition: (2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 2, 4, 1). The lexicographically smallest among them is (2, 1, 3, 4).
Sample Input 2
2 3 1 2 1 2 2 1
Sample Output 2
-1
No permutations P satisfy the condition.