Find Array A

Time limit2sMemory limit512 MB

Summary

Find the lexicographically smallest array A that comes after B and satisfies A[i] < A[j] for every given pair, with values up to 2*10^9.

Level: Medium7 of 10
Topics: Graph, Topological sort, Greedy
Solved: No attempts yet

Problem

Find an array A that satisfies the following conditions.

Its size is N, and every element is a natural number less than or equal to $2 \times 10^9$ .
It comes after the array B of size N in lexicographical order.
For each of the M pairs $(i, j)$ , $A[i] < A[j]$ holds.

Input

The first line contains N and M, the size of the array and the number of pairs. The second line contains $B[1], B[2], \ldots, B[N]$ . From the third line on, each of the M lines contains $i$ and $j$ , meaning $A[i] < A[j]$ must hold.

Output

Print the lexicographically smallest array A that satisfies the conditions. If no array satisfies the conditions, print -1.

Constraints

$1 \le N \le 100{,}000$
$0 \le M \le 100{,}000$
$1 \le B[i] \le 10^9$
$1 \le i, j \le N$ , $i \ne j$

Examples4

Example 1
Input
```
3 2
1 2 3
2 1
1 3
```
Expected output
```
2 1 3
```
Example 2
Input
```
3 2
1 2 3
2 1
1 2
```
Expected output
```
-1
```
Example 3
Input
```
3 0
1 2 3
```
Expected output
```
1 2 4
```

Example 4

Input

9 10
2 4 3 5 1 7 2 9 3
1 9
1 4
2 4
3 5
5 7
4 7
5 6
7 6
6 8
7 8

Expected output

2 4 3 5 4 7 6 8 3