题目描述

给定整数 $N$ 和 $M$ 个约束条件 $(A_i,B_i)$，求满足以下条件的排列 $P$ （字典序最小）：

1. $P$ 是 $(1,2,...,N)$ 的一个排列
2. 对于每个约束条件 $(A_i,B_i)$，在 $P$ 中 $A_i$ 必须出现在 $B_i$ 之前

如果不存在这样的排列，输出-1。

输入格式

输入格式如下：

$N$ $M$

$A₁$ $B₁$

$A₂$ $B₂$

$\dots$

$A_M$ $B_M$

输出格式

输出满足条件的字典序最小排列，或-1。

输入输出样例

样例1输入：

4 3
2 1
3 4
2 4

样例1输出：

2 1 3 4

说明：满足条件的排列有5种，其中字典序最小的是$(2,1,3,4)$

样例2输入：

2 3
1 2
1 2
2 1

样例2输出：

-1

说明：存在矛盾约束（既要求1在2前，又要求2在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$
• 所有输入均为整数