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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class T1>
void deb(T1 e1) {
  cout << e1 << endl;
}
template <class T1, class T2>
void deb(T1 e1, T2 e2) {
  cout << e1 << " " << e2 << endl;
}
template <class T1, class T2, class T3>
void deb(T1 e1, T2 e2, T3 e3) {
  cout << e1 << " " << e2 << " " << e3 << endl;
}
template <class T1, class T2, class T3, class T4>
void deb(T1 e1, T2 e2, T3 e3, T4 e4) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << endl;
}
template <class T1, class T2, class T3, class T4, class T5>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << endl;
}
template <class T1, class T2, class T3, class T4, class T5, class T6>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5, T6 e6) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << " " << e6
       << endl;
}
const long long int mod = 1000000007ll;
vector<int> alive[300005];
vector<int> adj[300005];
vector<int> radj[300005];
int col[300005];
int val[300005];
int deg[300005];
bool possible(int n, int k) {
  queue<int> qu;
  for (int i = 1; i <= n; i++) {
    deg[i] = adj[i].size();
    if (deg[i] == 0) {
      qu.push(i);
      if (col[i] == 0)
        val[i] = 1;
      else
        val[i] = col[i];
    }
  }
  while (!qu.empty()) {
    int u = qu.front();
    qu.pop();
    if (col[u] != 0) {
      if (val[u] > col[u]) return false;
      val[u] = col[u];
    }
    for (int i = 0; i < radj[u].size(); i++) {
      int v = radj[u][i];
      deg[v]--;
      val[v] = max(val[v], val[u] + 1);
      if (deg[v] == 0) {
        qu.push(v);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (val[i] == 0 || val[i] > k) return false;
  }
  return true;
}
int cnt[300005];
bool solve(int n, int k) {
  priority_queue<pair<int, int> > qu;
  for (int i = 1; i <= n; i++) {
    deg[i] = radj[i].size();
    if (deg[i] == 0) {
      if (col[i] == 0)
        qu.push(make_pair(val[i], i));
      else
        alive[col[i]].push_back(i);
    }
    cnt[val[i]]++;
  }
  int make = k;
  while (make > 0) {
    while (make > 0 && cnt[make] != 0) {
      for (int i = 0; i < alive[make].size(); i++)
        qu.push(make_pair(val[alive[make][i]], alive[make][i]));
      make--;
    }
    if (qu.empty()) return false;
    int u = qu.top().second;
    qu.pop();
    for (int i = 0; i < adj[u].size(); i++) {
      int v = adj[u][i];
      deg[v]--;
      if (deg[v] == 0) {
        if (col[v] == 0 || col[v] >= make)
          qu.push(make_pair(val[v], v));
        else {
          alive[col[v]].push_back(v);
        }
      }
    }
    if (make == 0) continue;
    if (val[u] >= make || col[u] != 0) continue;
    cnt[val[u]]--;
    val[u] = make;
    cnt[val[u]]++;
  }
  memset(deg, 0, sizeof deg);
  for (int i = 1; i <= n; i++) deg[val[i]]++;
  for (int i = 1; i <= k; i++)
    if (deg[i] == 0) return false;
  return true;
}
int main() {
  int n, m, k, u, v;
  scanf("%d %d %d", &n, &m, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &col[i]);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", &u, &v);
    adj[u].push_back(v);
    radj[v].push_back(u);
  }
  if (!possible(n, k)) {
    puts("-1");
    return 0;
  }
  if (!solve(n, k)) {
    puts("-1");
    return 0;
  }
  for (int i = 1; i <= n; i++) printf("%d ", val[i]);
  puts("");
  return 0;
}