题目描述

将 $( 1,2,\dots,n )$ 重新排列后得到一个数列 $P$，满足对于 $\forall i\in [1,m]$，$P$ 中的 $a_i$ 要出现在 $b_i$ 之前。在此前提下要求 $P$ 的字典序最小。如果不存在这样的 $P$，请输出 $-1$。

输入格式

第一行为两个数 $n,m(1\le n,m\le 2 \times 10^5)$，其中 $m$。

往下 $m$ 行每一行为 $a_i,b_i$。

输出格式

存在这样的 $P$，则直接输出，否则输出 $-1$。

4 3
2 1
3 4
2 4

2 1 3 4

2 3
1 2
1 2
2 1

-1