Problem: There are n military men in the Berland army. Some of them have given orders to other military men by now. Given m pairs (xi, yi), meaning that the military man xi gave the i-th order to another military man yi.

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 xi) is strictly greater than the rank of a person receiving the order (military man yi); 
  * 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·105, 0 ≤ m ≤ 2·105, 1 ≤ k ≤ 2·105) — number of military men in the Berland army, number of orders and number of ranks.

The second line contains n integers r1, r2, ..., rn, where ri > 0 (in this case 1 ≤ ri ≤ k) means that the i-th military man has been already assigned the rank ri; ri = 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 xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi). This line means that the i-th order was given by the military man xi to the military man yi. 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

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main2{
	static LinkedList<Integer>[]adj,adjRev;
	static int[]maxDep,size,maxVal;
	static TreeSet<Integer>ava;
	static int[]val;
	static int[]v;
	static int notvis=0,notF=1,f=2;
	static boolean cycle;
	static void dfs(int i) {
		v[i]=notF;
		for(int j:adj[i]) {
			if(v[j]==notF) {
				cycle=true;
			}
			else {
				if(v[j]==notvis) {
					dfs(j);
				}
			}
		}
		v[i]=f;
	}
	static void pre(int i) {
		maxDep[i]=1;
		size[i]=1;
		if(val[i]!=0) {
			maxVal[i]=val[i];
		}
		for(int j:adjRev[i]) {
			if(maxDep[j]==-1) {
				pre(j);
			}
			maxDep[i]=Math.max(maxDep[i], maxDep[j]+1);
			maxVal[i]=Math.min(maxVal[i], maxVal[j]-1);
			size[i]+=size[j];
		}
		maxVal[i]=Math.min(maxVal[i], originalk-maxDep[i]+1);
	}
	static int originalk;
	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		int k=Integer.parseInt(st.nextToken());
		originalk=k;
		if(k>n) {
			System.out.println(-1);
			return;
		}
		ava=new TreeSet<Integer>();
		adj=new LinkedList[n];
		adjRev=new LinkedList[n];
		maxDep=new int[n];
		size=new int[n];
		maxVal=new int[n];
		v=new int[n];
		val=new int[n];
		boolean[]notRoot=new boolean[n];
		for(int i=0;i<n;i++) {
			adj[i]=new LinkedList<Integer>();
			adjRev[i]=new LinkedList<Integer>();
			maxDep[i]=-1;
			size[i]=0;
			maxVal[i]=1000000089;
			
		}
		for(int i=0;i<k;i++)ava.add(i+1);
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			val[i]=Integer.parseInt(st.nextToken());
			if(val[i]!=0)
				ava.remove(val[i]);
		}
		for(int i=0;i<m;i++) {
			st=new StringTokenizer(br.readLine());
			int x=Integer.parseInt(st.nextToken())-1,y=Integer.parseInt(st.nextToken())-1;
			adj[x].add(y);
			adjRev[y].add(x);
			notRoot[y]=true;
		}
		for(int i=0;i<n;i++) {
			if(v[i]==0)dfs(i);
		}
		if(cycle) {
			System.out.println(-1);
			return;
		}
		for(int i=0;i<n;i++) {
			if(maxDep[i]==-1) {
				pre(i);
			}
		}
		for(int i=0;i<n;i++) {
			if(maxVal[i]<=0) {
				System.out.println(-1);
				return;
			}
			if(val[i]!=0 && val[i]>maxVal[i]) {
				System.out.println(-1);
				return;
			}
			v[i]=0;
		}
		PriorityQueue<Integer>q=new PriorityQueue<Integer>((x,y)->maxVal[x]-maxVal[y]);
		int[]deg=new int[n];
		int[]minVal=new int[n];
		for(int i=0;i<n;i++) {
			deg[i]=adj[i].size();
		}
		for(int i=0;i<n;i++) {
			if(deg[i]==0) {
				q.add(i);
			}
		}
//		System.out.println(ava+" "+Arrays.toString(maxVal)+" "+q+" "+maxDep[4]);
		while(!q.isEmpty()) {
			int cur=q.poll();
			if(val[cur]==0) {
				Integer cand=ava.higher(minVal[cur]);
				val[cur]=cand!=null?cand:(minVal[cur]+1);
				if(val[cur]>maxVal[cur]) {
					val[cur]=maxVal[cur];
				}
			}
			for(int j:adjRev[cur]) {
				deg[j]--;
				minVal[j]=Math.max(minVal[j], val[cur]);
				if(deg[j]==0) {
					q.add(j);
				}
			}
			ava.remove(val[cur]);
		}
//		System.out.println(ava);
		if(!ava.isEmpty()) {
			System.out.println(-1);
			return;
		}
		PrintWriter pw=new PrintWriter(System.out);
		for(int i=0;i<n;i++)pw.print((val[i])+" ");
		pw.println();
		pw.flush();
	}
}