A11456 | Berland Army

There 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.

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$ .

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.