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.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class A {
	static int dis(int x, int y, int x2, int y2) {

		return Math.abs(x - x2) + Math.abs(y - y2);
	}

	static int parseInt(String s) {
		return Integer.parseInt(s);
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);

		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		int[] ranks = sc.nextIntArr(n);
		ArrayList<Integer>[] adj = new ArrayList[n];
		ArrayList<Integer>[] adjrev = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			adj[i] = new ArrayList<Integer>();
			adjrev[i] = new ArrayList<Integer>();
		}
		int[] deg = new int[n];
		while (m-- > 0) {
			int u = sc.nextInt() - 1;
			int v = sc.nextInt() - 1;
			adj[u].add(v);
			adjrev[v].add(u);
			deg[u]++;
		}
		Queue<Integer> q = new LinkedList<Integer>();

		for (int i = 0; i < n; i++)
			if (deg[i] == 0)
				q.add(i);

		int[] order = new int[n];
		int[] max = new int[n];
		int id = 0;
		while (!q.isEmpty()) {
			int cur = q.poll();
			order[id++] = cur;
			max[cur] = Math.max(ranks[cur] - 1, max[cur]);

			for (int v : adjrev[cur]) {
				if (--deg[v] == 0) {
					q.add(v);
				}
				max[v] = Math.max(max[v], 1 + max[cur]);
			}
		}
		Integer[] nodes = new Integer[n];
		if (id != n) {
			pw.println(-1);
		} else {
			TreeSet<Integer> ts = new TreeSet<>();
			for (int i = 1; i <= k; i++)
				ts.add(i);
			for (int v : ranks)
				ts.remove(v);
			// System.err.println(ts);

			for (int i = 0; i < n; i++)
				nodes[i] = i;
			Arrays.sort(nodes, (x, y) -> max[y] - max[x]);
			// System.err.println(Arrays.toString(max));
			boolean valid = true;
			for (int i = 0; i < n; i++) {
				int cur = nodes[i];
				if (ranks[cur] != 0)
					continue;
				int v = k;
				for (int nxt : adjrev[cur]) {
					v = Math.min(v, ranks[nxt] - 1);
				}
				// System.err.println(v + " " + cur + " vsd");
				if (ts.floor(v) != null && ts.floor(v) > (max[cur])) {
					int t = ts.floor(v);
					ts.remove(t);
					ranks[cur] = t;
				} else {
					if (max[cur] >= k)
						valid = false;

					ranks[cur] = k;
					for (int nxt : adjrev[cur]) {
						ranks[cur] = Math.min(ranks[cur], ranks[nxt] - 1);
					}
				}
				// System.err.println(cur + " " + ranks[cur]);

				if (ranks[cur] <= 0)
					valid = false;
			}
			for (int i = 0; i < n; i++)
				if (ranks[i] <= max[i])
					valid = false;
			if (!ts.isEmpty() || !valid) {
				pw.println(-1);
			} else {
				for (int x : ranks)
					pw.print(x + " ");
				pw.println();
			}

		}
		pw.flush();
	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader f) {
			br = new BufferedReader(f);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArr(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(next());
			}
			return arr;
		}

	}

}