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.
import java.util.*;
import java.io.*;

// Solution

public class Main 
{    
  public static void main (String[] argv)
  {
	  new Main();
  } 
     
     
  
  boolean test = false;  
  
  
  public Main() {
	  FastReader in = new FastReader(new BufferedReader(new InputStreamReader(System.in)));
	  //FastReader in = new FastReader(new BufferedReader(new FileReader("Main.in")));
      int n = in.nextInt();
      int m = in.nextInt();
      int[] ideg = new int[n];
      List<Integer>[] nbs = new List[n];      
      String s = in.next();
     
      for(int i = 0;  i < n; i++) {
          nbs[i] = new ArrayList<>();
      }
      
      for (int i = 0; i < m; i++) {
          int p = in.nextInt() - 1;
          int q = in.nextInt() - 1;
          
          nbs[p].add(q);
          ++ideg[q];
      }
      
      //bfs
      int R = 26;
      int[][] dp = new int[n][R];      
      Deque<Integer> q = new ArrayDeque<>(n);
      for (int i = 0; i < n; i++) {
          if (ideg[i] == 0) {
              q.add(i);              
          }
      }
      int nVisited = 0;
      int ans = 0;
      while (!q.isEmpty()) {
          int cur = q.remove();
          
          ++nVisited;
          int icur = s.charAt(cur) - 'a';
          dp[cur][icur]++;
          ans = max(ans, dp[cur][icur]);
          for (int next : nbs[cur]) {             
              
              int idn = s.charAt(next) - 'a';
              for (int i = 0; i < R; i++) {
                  dp[next][i] = max(dp[next][i], dp[cur][i]);
                  ans = max(ans, dp[next][i]);                  
              }
              
              --ideg[next];
              if (ideg[next] == 0) q.add(next);
          }
          
      }
      
      if(nVisited < n)
          System.out.println(-1);
      else System.out.println(ans);
     
  }
  
  
  private long gcd(long x, long y) {
      if (y == 0) return x;
      return gcd(y, x % y);
  }
  private int max(int a, int b) {
      return a >  b ? a : b;
  }
  
  private int min(int a, int b) {
      return a >  b ? b : a;
  }
  
  
  static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader(BufferedReader in)
        {            
            br = in;
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    String line = br.readLine();
                    if (line == null || line.length() == 0) return "";
                    st = new StringTokenizer(line);
                }
                catch (IOException  e)
                {
                    return "";
                    //e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                return "";
                //e.printStackTrace();
            }
            return str;
        }
    }
}