You are given a program you want to execute as a set of tasks organized in a dependency graph. The dependency graph is a directed acyclic graph: each task can depend on results of one or several other tasks, and there are no directed circular dependencies between tasks. A task can only be executed if all tasks it depends on have already completed.

Some of the tasks in the graph can only be executed on a coprocessor, and the rest can only be executed on the main processor. In one coprocessor call you can send it a set of tasks which can only be executed on it. For each task of the set, all tasks on which it depends must be either already completed or be included in the set. The main processor starts the program execution and gets the results of tasks executed on the coprocessor automatically.

Find the minimal number of coprocessor calls which are necessary to execute the given program.

Input

The first line contains two space-separated integers N (1 ≤ N ≤ 105) — the total number of tasks given, and M (0 ≤ M ≤ 105) — the total number of dependencies between tasks.

The next line contains N space-separated integers <image>. If Ei = 0, task i can only be executed on the main processor, otherwise it can only be executed on the coprocessor.

The next M lines describe the dependencies between tasks. Each line contains two space-separated integers T1 and T2 and means that task T1 depends on task T2 (T1 ≠ T2). Tasks are indexed from 0 to N - 1. All M pairs (T1, T2) are distinct. It is guaranteed that there are no circular dependencies between tasks.

Output

Output one line containing an integer — the minimal number of coprocessor calls necessary to execute the program.

Examples

Input

4 3
0 1 0 1
0 1
1 2
2 3


Output

2


Input

4 3
1 1 1 0
0 1
0 2
3 0


Output

1

Note

In the first test, tasks 1 and 3 can only be executed on the coprocessor. The dependency graph is linear, so the tasks must be executed in order 3 -> 2 -> 1 -> 0. You have to call coprocessor twice: first you call it for task 3, then you execute task 2 on the main processor, then you call it for for task 1, and finally you execute task 0 on the main processor.

In the second test, tasks 0, 1 and 2 can only be executed on the coprocessor. Tasks 1 and 2 have no dependencies, and task 0 depends on tasks 1 and 2, so all three tasks 0, 1 and 2 can be sent in one coprocessor call. After that task 3 is executed on the main processor.
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
int ni() {
  int val;
  scanf("%i", &val);
  return val;
}
pair<int, int> npi() {
  pair<int, int> val;
  scanf("%i %i", &val.first, &val.second);
  return val;
}
int64_t nll() {
  int64_t val;
  scanf("%I64d", &val);
  return val;
}
vector<int> nvi(int n, int corr = 0) {
  vector<int> a(n);
  for (int i = 0; i < n; ++i) a[i] = ni() + corr;
  return move(a);
}
char nc() {
  char val;
  do {
    val = getchar();
  } while (val == ' ' || val == '\r' || val == '\n');
  return val;
}
char ncs() {
  char val;
  do {
    val = getchar();
  } while (false);
  return val;
}
string ns() {
  static char buff[1024 * 4000];
  scanf("%s", buff);
  return string{buff};
}
int64_t gcd(int64_t a, int64_t b) {
  while (b) {
    auto tmp = a % b;
    a = b;
    b = tmp;
  }
  return a;
}
int64_t tr2(int xv1, int yv1, int xv2, int yv2, int x3, int y3) {
  return 1LL * (xv2 - xv1) * (y3 - yv1) - 1LL * (yv2 - yv1) * (x3 - xv1);
}
const long double eps = 1e-12;
const long double pi = acos(-1.0);
bool eq(long double a, long double b) { return abs(a - b) <= eps; }
int8_t bits_cnt[256];
const string input_dir = "inputs\\";
string input_file = input_dir + "input.txt";
string output_file = input_dir + "output.txt";
void init_streams() {}
void init_data() {
  for (int i = 1; i <= 255; ++i)
    for (int j = 0; j < 8; ++j)
      if ((1 << j) & i) ++bits_cnt[i];
}
int bit_count(int v) {
  return bits_cnt[v & 0xFF] + bits_cnt[(v >> 8) & 0xFF] +
         bits_cnt[(v >> 16) & 0xFF] + bits_cnt[(v >> 24) & 0xFF];
}
const int maxn = 100000 + 1;
int n, m;
int E[maxn];
std::vector<int> adj[maxn];
bool vis[maxn];
int mx[maxn];
int dfs(int u) {
  if (vis[u]) return mx[u];
  vis[u] = true;
  mx[u] = E[u];
  for (auto to : adj[u]) mx[u] = max(mx[u], (E[u] && !E[to]) + dfs(to));
  return mx[u];
}
int main() {
  init_streams();
  init_data();
  auto n = ni(), m = ni();
  for (int i = 0; i < n; ++i) E[i] = ni();
  for (int i = 0; i < m; ++i) {
    auto u = ni();
    auto v = ni();
    adj[u].emplace_back(v);
  }
  int ans = 0;
  for (int i = 0; i < n; ++i) ans = max(ans, dfs(i));
  cout << ans << endl;
  return 0;
}
