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 C>
void mini(C& a4, C b4) {
  a4 = min(a4, b4);
}
template <class C>
void maxi(C& a4, C b4) {
  a4 = max(a4, b4);
}
const int maxn = 2e5 + 1000;
vector<int> In[maxn];
vector<int> Out[maxn];
int r[maxn];
bool wsrodku[maxn];
int dp[maxn];
int n, m, k;
void niedasie() {
  puts("-1");
  exit(0);
}
int ustal(int x) {
  if (wsrodku[x]) niedasie();
  if (dp[x] != 0) return dp[x];
  wsrodku[x] = true;
  int minne = 0;
  for (int y : Out[x]) maxi(minne, ustal(y));
  ++minne;
  if (r[x] > 0) {
    if (r[x] < minne) niedasie();
    dp[x] = r[x];
  } else {
    if (minne > k)
      niedasie();
    else
      dp[x] = minne;
  }
  wsrodku[x] = false;
  return dp[x];
}
int u[maxn];
int najw[maxn];
int ile[maxn];
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = (0); i <= ((int)(n)-1); i++) scanf("%d", &r[i]);
  for (int i = (0); i <= ((int)(m)-1); i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    --x;
    --y;
    Out[x].push_back(y);
    In[y].push_back(x);
  }
  vector<pair<int, int> > V;
  for (int i = (0); i <= ((int)(n)-1); i++)
    V.push_back(pair<int, int>(ustal(i), i));
  sort(V.rbegin(), V.rend());
  for (int i = (0); i <= ((int)(n)-1); i++) u[i] = ustal(i);
  for (int i = (0); i <= ((int)(n)-1); i++) najw[i] = k;
  for (pair<int, int> p : V) {
    int x = p.second;
    if (r[x] != 0)
      najw[x] = r[x];
    else {
      for (int y : In[x]) mini(najw[x], najw[y] - 1);
    }
  }
  priority_queue<vector<int> > pq;
  priority_queue<int> puste;
  for (int i = (0); i <= ((int)(n)-1); i++) ++ile[u[i]];
  for (int i = (1); i <= (k); i++)
    if (ile[i] == 0) puste.push(i);
  for (pair<int, int> p : V) {
    int id = p.second;
    pq.push(vector<int>{najw[id], u[id], id});
    while (!puste.empty() && !pq.empty()) {
      while (!pq.empty() && pq.top()[1] > puste.top()) pq.pop();
      if (!pq.empty() && pq.top()[0] >= puste.top()) {
        int bylo = pq.top()[1];
        int jest = puste.top();
        id = pq.top()[2];
        pq.pop();
        puste.pop();
        --ile[bylo];
        ++ile[jest];
        u[id] = jest;
        if (ile[bylo] == 0) puste.push(bylo);
      } else
        break;
    }
  }
  if (!puste.empty()) niedasie();
  for (int i = (0); i <= ((int)(n)-1); i++) printf("%d ", u[i]);
  puts("");
}