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;
vector<int> g[300005], g2[300005];
char data[300005];
bool visit[300005];
int dp[300005][26];
vector<int> lst;
void dfs1(int node, int p) {
  visit[node] = 1;
  int len = g[node].size();
  for (int i = 0; i < len; i++) {
    int v = g[node][i];
    if (v != p && !visit[v]) {
      dfs1(v, node);
    }
  }
  lst.push_back(node);
}
int cnt;
void dfs2(int node, int p) {
  cnt++;
  visit[node] = 1;
  int len = g2[node].size();
  for (int i = 0; i < len; i++) {
    int v = g2[node][i];
    if (visit[v] == 0 && v != p) {
      dfs2(v, node);
    }
  }
}
int ans;
int solve(int node, int letter) {
  int &ret = dp[node][letter];
  if (ret != -1) return ret;
  ret = 0;
  int len = g[node].size();
  for (int i = 0; i < len; i++) {
    int v = g[node][i];
    ret = max(ret, solve(v, letter) + (letter == data[v] - 'a' ? 1 : 0));
  }
  return ret;
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) cin >> data[i];
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    g[a].push_back(b);
    if (a == b) ans = -1;
    g2[b].push_back(a);
  }
  for (int i = 1; i <= n; i++) {
    if (visit[i]) continue;
    dfs1(i, 0);
  }
  memset(visit, 0, sizeof visit);
  for (int i = n - 1; i >= 0; i--) {
    int v = lst[i];
    if (visit[v] == 0) {
      cnt = 0;
      dfs2(v, 0);
      if (cnt > 1) {
        ans = -1;
      }
    }
  }
  if (ans == -1) {
    cout << ans;
    return 0;
  }
  memset(dp, -1, sizeof dp);
  for (int i = 1; i <= 300000; i++) {
    for (int j = 0; j <= 25; j++) {
      ans = max(ans, solve(i, j) + (data[i] - 'a' == j));
    }
  }
  cout << ans << endl;
}
