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>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
void sleep(double sec = 1021) {
  clock_t s = clock();
  while (clock() - s < CLOCKS_PER_SEC * sec)
    ;
}
int __ = 1, _cs;
struct Scc {
  int n, nScc, vst[303030], bln[303030];
  vector<int> E[303030], rE[303030], vec;
  void init(int _n) {
    n = _n;
    for (int i = 0; i < 303030; i++) {
      E[i].clear();
      rE[i].clear();
    }
  }
  void add_edge(int u, int v) {
    E[u].push_back(v);
    rE[v].push_back(u);
  }
  void DFS(int u) {
    vst[u] = 1;
    for (auto v : E[u])
      if (!vst[v]) DFS(v);
    vec.push_back(u);
  }
  void rDFS(int u) {
    vst[u] = 1;
    bln[u] = nScc;
    for (auto v : rE[u])
      if (!vst[v]) rDFS(v);
  }
  int solve() {
    nScc = 0;
    vec.clear();
    memset(vst, 0, sizeof(vst));
    for (int i = 0; i < n; i++)
      if (!vst[i]) DFS(i);
    reverse(vec.begin(), vec.end());
    memset(vst, 0, sizeof(vst));
    for (auto v : vec) {
      if (!vst[v]) {
        rDFS(v);
        nScc++;
      }
    }
    return nScc;
  }
} graph;
void build() {}
int n, m;
char c[303030];
int *at;
int sz[303030], tot;
int ind[303030];
vector<int> topo, e[303030];
void topo_sort() {
  for (int i = 0; i < n; i++)
    for (int nxt : graph.E[i]) {
      if (at[i] == at[nxt]) continue;
      ind[at[nxt]]++;
      e[at[i]].push_back(at[nxt]);
    }
  for (int i = 0; i < tot; i++)
    if (ind[i] == 0) topo.push_back(i);
  for (size_t i = 0; i < topo.size(); i++) {
    int now = topo[i];
    for (int nxt : e[now]) {
      ind[nxt]--;
      if (ind[nxt] == 0) topo.push_back(nxt);
    }
  }
}
void init() {
  n = getint();
  m = getint();
  scanf("%s", c);
  graph.init(n);
  while (m--) {
    int ui = getint() - 1;
    int vi = getint() - 1;
    graph.add_edge(ui, vi);
    if (ui == vi) {
      puts("-1");
      exit(0);
    }
  }
  tot = graph.solve();
  at = graph.bln;
  for (int i = 0; i < n; i++) sz[at[i]]++;
}
int ans, dp[303030], bs[303030];
void solve() {
  topo_sort();
  for (int cc = 0; cc < 26; cc++) {
    for (int i = 0; i < tot; i++) dp[i] = bs[i] = 0;
    for (int i = 0; i < n; i++)
      if (c[i] == cc + 'a') bs[at[i]]++;
    for (int i = 0; i < tot; i++) dp[i] = bs[i];
    for (int i = 0; i < tot; i++)
      if (bs[i] and sz[i] > 1) {
        puts("-1");
        exit(0);
      }
    for (int i : topo) {
      for (int nxt : e[i]) dp[nxt] = max(dp[nxt], dp[i] + bs[nxt]);
      ans = max(ans, dp[i]);
    }
  }
  cout << ans << endl;
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}
