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>
const int kN = 3e5 + 10;
struct Node {
  struct Edge *fir;
  int in, id;
  int cntt[30];
} no[kN];
struct Edge {
  Node *to;
  Edge *nxt;
  Edge(Node *from, Node *to) : to(to), nxt(from->fir) {}
};
void add(Node *x, Node *y) { x->fir = new Edge(x, y); }
int n, m;
char s[kN];
int main() {
  scanf("%d%d ", &n, &m);
  for (int i = 1; i <= n; ++i) no[i].in = 0, no[i].id = i;
  scanf("%s", s + 1);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    add(&no[x], &no[y]);
    no[y].in++;
  }
  int qu[kN], l = 1, r = 0, cnt = 0, ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (no[i].in == 0) qu[++r] = i;
  }
  while (l <= r) {
    Node *v = &no[qu[l++]];
    cnt++;
    v->cntt[s[v->id] - 'a' + 1]++;
    for (int i = 1; i <= 26; ++i) ans = std::max(ans, v->cntt[i]);
    for (Edge *e = v->fir; e; e = e->nxt) {
      e->to->in--;
      if (e->to->in == 0) {
        qu[++r] = e->to->id;
      }
      for (int i = 1; i <= 26; ++i)
        e->to->cntt[i] = std::max(e->to->cntt[i], v->cntt[i]);
    }
  }
  if (cnt != n) {
    puts("-1");
  } else {
    printf("%d\n", ans);
  }
  return 0;
}
