7182: ABC223 —— D - Restricted Permutation
[Creator : ]
Description
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.
Input
Input is given from Standard Input in the following format:
$N\ M$
$A_1\ B_1$
$\vdots$
$A_M\ B_M$
$N\ M$
$A_1\ B_1$
$\vdots$
$A_M\ B_M$
Output
Print the answer.
Constraints
$2≤N≤2×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.
$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.
Sample 1 Input
4 3
2 1
3 4
2 4
Sample 1 Output
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 2 Input
2 3
1 2
1 2
2 1
Sample 2 Output
-1
No permutations P satisfy the condition.