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 namespace std;
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et() {
  puts("-1");
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) {
  long long z = y;
  while (x % y != 0) {
    z = x % y;
    x = y;
    y = z;
  }
  return z;
}
vector<int> mp[300105];
char s[300105];
int dfn[300105], sta[300105], low[300105], color, ii, cnt, belong[300105];
bool ins[300105];
void tarjan(int x, int p) {
  dfn[x] = low[x] = ++ii;
  sta[++cnt] = x;
  ins[x] = 1;
  for (auto child : mp[x]) {
    if (!dfn[child]) {
      tarjan(child, x);
      low[x] = min(low[x], low[child]);
    } else if (ins[child]) {
      low[x] = min(low[x], dfn[child]);
    }
  }
  if (dfn[x] == low[x]) {
    ++color;
    int t, cc = 0;
    do {
      t = sta[cnt];
      cnt--;
      ins[t] = 0;
      belong[t] = color;
      cc++;
      if (cc > 1) et();
    } while (dfn[t] != low[t]);
  }
}
int dis[300105], ans, Ans;
void dfs(int x, int ch) {
  if (dis[x] != -1) return;
  int cc = (s[x] - 'a' == ch);
  dis[x] = 0;
  for (int c : mp[x]) {
    dfs(c, ch);
    dis[x] = max(dis[x], dis[c]);
  }
  dis[x] += cc;
  ans = max(dis[x], ans);
}
void fmain(int ID) {
  scanf("%d%d", &n, &m);
  scanf("%s", s + 1);
  for (int(i) = 0; (i) < (int)(m); (i)++) {
    int u, v;
    scanf("%d%d", &u, &v);
    if (u == v) et();
    mp[u].push_back(v);
  }
  for (int(i) = 1; (i) <= (int)(n); (i)++)
    if (belong[i] == 0) tarjan(i, 0);
  for (int(j) = 0; (j) < (int)(26); (j)++) {
    memset(dis, -1, sizeof dis);
    ans = 0;
    for (int(x) = 1; (x) <= (int)(n); (x)++)
      if (dis[x] == -1) dfs(x, j);
    Ans = max(Ans, ans);
  }
  printf("%d\n", Ans);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}
