配点 : $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$

出力

答えを出力せよ。

4 3
2 1
3 4
2 4

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 3
1 2
1 2
2 1

-1

条件を満たす $P$ は存在しません。