You are given a graph with n nodes and m directed edges. One lowercase letter is assigned to each node. We define a path's value as the number of the most frequently occurring letter. For example, if letters on a path are "abaca", then the value of that path is 3. Your task is find a path whose value is the largest.

Input

The first line contains two positive integers n, m (1 ≤ n, m ≤ 300 000), denoting that the graph has n nodes and m directed edges.

The second line contains a string s with only lowercase English letters. The i-th character is the letter assigned to the i-th node.

Then m lines follow. Each line contains two integers x, y (1 ≤ x, y ≤ n), describing a directed edge from x to y. Note that x can be equal to y and there can be multiple edges between x and y. Also the graph can be not connected.

Output

Output a single line with a single integer denoting the largest value. If the value can be arbitrarily large, output -1 instead.

Examples

Input

5 4
abaca
1 2
1 3
3 4
4 5


Output

3


Input

6 6
xzyabc
1 2
3 1
2 3
5 4
4 3
6 4


Output

-1


Input

10 14
xzyzyzyzqx
1 2
2 4
3 5
4 5
2 6
6 8
6 5
2 10
3 9
10 9
4 6
1 10
2 8
3 7


Output

4

Note

In the first sample, the path with largest value is 1 → 3 → 4 → 5. The value is 3 because the letter 'a' appears 3 times.
#include <bits/stdc++.h>
using std ::max;
using std ::min;
template <class T>
bool chkmin(T &x, const T &y) {
  return y < x ? x = y, true : false;
}
template <class T>
bool chkmax(T &x, const T &y) {
  return y > x ? x = y, true : false;
}
class FastInput {
 private:
  static const int L = 1 << 15 | 1;
  char buffer[L], *_, *__;
  inline void Next(char &ch) {
    if (_ == __) __ = (_ = buffer) + fread(buffer, 1, L, stdin);
    ch = _ == __ ? EOF : *_++;
  }

 public:
  template <class T>
  void operator()(T &in) {
    char ch;
    int f = 1;
    for (Next(ch); !isdigit(ch); Next(ch))
      if (ch == '-') f = -1;
    for (in = 0; isdigit(ch); Next(ch)) in = in * 10 + ch - '0';
    in *= f;
  }
};
const int maxx = 300000 + 25;
int n, m, x, y, z, k, num;
int tot, len, top, ans;
int skt[maxx], in[maxx], vis[maxx];
int head[maxx], to[maxx], nxt[maxx];
int u[maxx], v[maxx], f[maxx];
char s[maxx];
void Ins(int x, int y) {
  to[++num] = y;
  nxt[num] = head[x];
  head[x] = num;
}
void Get(int li) {
  memset(head, 0, sizeof(head));
  num = 0;
  memset(f, 0, sizeof(f));
  for (int i = (1), i_END = (m); i <= (i_END); ++i) {
    Ins(u[i], v[i]);
    ++in[v[i]];
  }
  for (int i = (1), i_END = (n); i <= (i_END); ++i) {
    if (!in[i]) {
      skt[++top] = i;
      if (s[i] == li + 'a' - 1) f[i] = 1;
    }
  }
  while (top) {
    x = skt[top--];
    for (int i = head[x]; i; i = nxt[i]) {
      chkmax(f[to[i]], f[x] + (s[to[i]] == li + 'a' - 1));
      --in[to[i]];
      if (!in[to[i]]) skt[++top] = to[i];
    }
  }
  int tmp = 0;
  for (int i = (1), i_END = (n); i <= (i_END); ++i) chkmax(tmp, f[i]);
  chkmax(ans, tmp);
}
int main() {
  scanf("%d%d", &n, &m);
  scanf("%s", s + 1);
  for (int i = (1), i_END = (m); i <= (i_END); ++i) {
    scanf("%d%d", &x, &y);
    Ins(x, y);
    ++in[y];
    u[i] = x;
    v[i] = y;
  }
  for (int i = (1), i_END = (n); i <= (i_END); ++i)
    if (!in[i]) skt[++top] = i, vis[i] = 1;
  while (top) {
    x = skt[top--];
    for (int i = head[x]; i; i = nxt[i]) {
      --in[to[i]];
      if (!in[to[i]]) {
        vis[skt[++top] = to[i]] = 1;
      }
    }
  }
  for (int i = (1), i_END = (n); i <= (i_END); ++i) {
    if (!vis[i]) {
      puts("-1");
      return 0;
    }
  }
  for (int i = (1), i_END = (26); i <= (i_END); ++i) Get(i);
  printf("%d\n", ans);
  return 0;
}
