No tag edit access

B. Berland Army

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere are *n* military men in the Berland army. Some of them have given orders to other military men by now. Given *m* pairs (*x*_{i}, *y*_{i}), meaning that the military man *x*_{i} gave the *i*-th order to another military man *y*_{i}.

It is time for reform! The Berland Ministry of Defence plans to introduce ranks in the Berland army. Each military man should be assigned a rank — integer number between 1 and *k*, inclusive. Some of them have been already assigned a rank, but the rest of them should get a rank soon.

Help the ministry to assign ranks to the rest of the army so that:

- for each of
*m*orders it is true that the rank of a person giving the order (military man*x*_{i}) is strictly greater than the rank of a person receiving the order (military man*y*_{i}); - for each rank from 1 to
*k*there is at least one military man with this rank.

Input

The first line contains three integers *n*, *m* and *k* (1 ≤ *n* ≤ 2·10^{5}, 0 ≤ *m* ≤ 2·10^{5}, 1 ≤ *k* ≤ 2·10^{5}) — number of military men in the Berland army, number of orders and number of ranks.

The second line contains *n* integers *r*_{1}, *r*_{2}, ..., *r*_{n}, where *r*_{i} > 0 (in this case 1 ≤ *r*_{i} ≤ *k*) means that the *i*-th military man has been already assigned the rank *r*_{i}; *r*_{i} = 0 means the *i*-th military man doesn't have a rank yet.

The following *m* lines contain orders one per line. Each order is described with a line containing two integers *x*_{i}, *y*_{i} (1 ≤ *x*_{i}, *y*_{i} ≤ *n*, *x*_{i} ≠ *y*_{i}). This line means that the *i*-th order was given by the military man *x*_{i} to the military man *y*_{i}. For each pair (*x*, *y*) of military men there could be several orders from *x* to *y*.

Output

Print *n* integers, where the *i*-th number is the rank of the *i*-th military man. If there are many solutions, print any of them.

If there is no solution, print the only number -1.

Examples

Input

5 3 3

0 3 0 0 2

2 4

3 4

3 5

Output

1 3 3 2 2

Input

7 6 5

0 4 5 4 1 0 0

6 1

3 6

3 1

7 5

7 1

7 4

Output

2 4 5 4 1 3 5

Input

2 2 2

2 1

1 2

2 1

Output

-1

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/26/2018 16:45:02 (f2).

Desktop version, switch to mobile version.

User lists

Name |
---|