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;
void fast() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
vector<char> s;
char ch;
set<int> v[300009], V[300009];
vector<vector<int> > dp(300009);
vector<bool> vis(300009, false);
class Graph {
  int V;
  list<int> *adj;
  bool isCyclicUtil(int v, bool visited[], bool *rs);

 public:
  Graph(int V);
  void addEdge(int v, int w);
  bool isCyclic();
};
Graph::Graph(int V) {
  this->V = V;
  adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) { adj[v].push_back(w); }
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack) {
  if (visited[v] == false) {
    visited[v] = true;
    recStack[v] = true;
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i) {
      if (!visited[*i] && isCyclicUtil(*i, visited, recStack))
        return true;
      else if (recStack[*i])
        return true;
    }
  }
  recStack[v] = false;
  return false;
}
bool Graph::isCyclic() {
  bool *visited = new bool[V];
  bool *recStack = new bool[V];
  for (int i = 0; i < V; i++) {
    visited[i] = false;
    recStack[i] = false;
  }
  for (int i = 0; i < V; i++)
    if (isCyclicUtil(i, visited, recStack)) return true;
  return false;
}
vector<int> dfs(int x) {
  if (vis[x] == true) return dp[x];
  vis[x] = true;
  vector<int> ans(26, 0);
  set<int>::iterator it = V[x].begin();
  while (it != V[x].end()) {
    vector<int> tans = dfs(*it);
    for (int i = 0; i < 26; i++) ans[i] = max(ans[i], tans[i]);
    it++;
  }
  ans[s[x] - 'a']++;
  dp[x] = ans;
  return ans;
}
int main() {
  int n, m;
  cin >> n >> m;
  int i;
  s.resize(n + 1);
  Graph g(n + 1);
  for (i = 1; i <= n; i++) {
    dp[i].resize(26, 0);
    cin >> s[i];
  }
  while (m--) {
    int x, y;
    cin >> x >> y;
    if (x == y) {
      cout << -1;
      return 0;
    }
    g.addEdge(x, y);
    v[x].insert(y);
    V[y].insert(x);
  }
  if (g.isCyclic()) {
    cout << -1 << '\n';
    return 0;
  }
  int max_ans = 0;
  for (i = 1; i <= n; i++) {
    if (v[i].size() == 0) {
      vector<int> Ans;
      Ans = dfs(i);
      for (int j = 0; j < 26; j++) max_ans = max(max_ans, Ans[j]);
    }
  }
  cout << max_ans << '\n';
  return 0;
}
