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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 200000;
const int MAXRANK = 200000;
struct P {
  int mxrank, mnrank, id;
};
bool operator<(const P &a, const P &b) {
  if (a.mxrank != b.mxrank) return a.mxrank > b.mxrank;
  return a.id < b.id;
}
int n, m, nrank;
int fixedrank[MAXN];
vector<int> e[MAXN];
vector<int> re[MAXN];
P p[MAXN];
int ans[MAXN];
queue<int> q[MAXRANK];
int deg[MAXN];
void calcmxrank() {
  for (int i = (0); i < (nrank); ++i) q[i] = queue<int>();
  for (int i = (0); i < (n); ++i)
    deg[i] = ((int)(re[i]).size()), p[i].mxrank = -1;
  for (int i = (0); i < (n); ++i)
    if (deg[i] == 0) {
      int x = fixedrank[i] == -1 ? nrank - 1 : fixedrank[i];
      q[x].push(i);
    }
  for (int r = nrank - 1; r >= 0; --r) {
    while (!q[r].empty()) {
      int at = q[r].front();
      q[r].pop();
      p[at].mxrank = r;
      for (int i = (0); i < (((int)(e[at]).size())); ++i) {
        int to = e[at][i];
        if (--deg[to] == 0) {
          int x = fixedrank[to] == -1 ? r - 1 : fixedrank[to];
          if (0 <= x && x < r) q[x].push(to);
        }
      }
    }
  }
}
void calcmnrank() {
  for (int i = (0); i < (nrank); ++i) q[i] = queue<int>();
  for (int i = (0); i < (n); ++i)
    deg[i] = ((int)(e[i]).size()), p[i].mnrank = -1;
  for (int i = (0); i < (n); ++i)
    if (deg[i] == 0) {
      int x = fixedrank[i] == -1 ? 0 : fixedrank[i];
      q[x].push(i);
    }
  for (int r = (0); r < (nrank); ++r) {
    while (!q[r].empty()) {
      int at = q[r].front();
      q[r].pop();
      p[at].mnrank = r;
      for (int i = (0); i < (((int)(re[at]).size())); ++i) {
        int to = re[at][i];
        if (--deg[to] == 0) {
          int x = fixedrank[to] == -1 ? r + 1 : fixedrank[to];
          if (r < x && x < nrank) q[x].push(to);
        }
      }
    }
  }
}
priority_queue<pair<int, int> > pq;
bool calcans() {
  sort(p, p + n);
  pq = priority_queue<pair<int, int> >();
  int at = 0;
  for (int r = nrank - 1; r >= 0; --r) {
    while (at < n && p[at].mxrank == r) {
      pq.push(make_pair(p[at].mnrank, -p[at].id));
      ++at;
    }
    if (pq.empty()) return false;
    int cur = -pq.top().second;
    pq.pop();
    ans[cur] = r;
    while (!pq.empty() && pq.top().first == r) {
      int oth = -pq.top().second;
      pq.pop();
      ans[oth] = r;
    }
  }
  return true;
}
bool solve() {
  for (int i = (0); i < (n); ++i) p[i].id = i;
  calcmxrank();
  calcmnrank();
  for (int i = (0); i < (n); ++i)
    if (p[i].mnrank == -1 || p[i].mxrank == -1 || p[i].mnrank > p[i].mxrank)
      return false;
  return calcans();
}
void run() {
  scanf("%d%d%d", &n, &m, &nrank);
  for (int i = (0); i < (n); ++i) scanf("%d", &fixedrank[i]), --fixedrank[i];
  for (int i = (0); i < (m); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a, --b;
    e[a].push_back(b);
    re[b].push_back(a);
  }
  if (!solve()) {
    printf("-1\n");
    return;
  }
  for (int i = (0); i < (n); ++i) {
    if (i != 0) printf(" ");
    printf("%d", ans[i] + 1);
  }
  puts("");
}
int main() {
  run();
  return 0;
}