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.
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
//System.out.println();
public class Graph
{   public static boolean visited[];
    public static boolean checked[];
    public static boolean flag;
    public static char val[];
    public static int dp[][];
    public static ArrayList adj[];
    
    public Graph(int n, String s1) {
        visited = new boolean[n];
        checked = new boolean[n];
        dp = new int[n][26];
        flag = false;
        val = new char[n];
        adj = new ArrayList[n];
        
        for(int i = 0; i < n; i++) {
            adj[i] = new ArrayList();
            val[i] = s1.charAt(i);
            visited[i] = false;
            checked[i] = false;
            dp[i][(int)val[i] - 97] = 1;
        }
    }
    
    public void dfs(int root) {
        if(adj[root].size() == 0) {
            return;
        }
        
        Iterator itr = adj[root].iterator();
        while(itr.hasNext()) {
            int node = (int)itr.next();
            
            if(checked[node]) {
                flag = true;
                break;
            }
            
            if(visited[node]) {
                for(int i = 0; i < 26; i++) {
                    if(i == (int)val[root] - 97)
                    dp[root][i] = Math.max(dp[root][i], 1 + dp[node][i]);
                    else
                    dp[root][i] = Math.max(dp[root][i], dp[node][i]);
                }
                continue;
            }
            
            checked[node] = true;
            visited[node] = true;
            dfs(node);
            for(int i = 0; i < 26; i++) {
                    if(i == (int)val[root] - 97)
                    dp[root][i] = Math.max(dp[root][i], 1 + dp[node][i]);
                    else
                    dp[root][i] = Math.max(dp[root][i], dp[node][i]);
                }
            checked[node] = false;
        }
        
        return;
        
    }
    
    public static int findMax(int node) {
       int ans = 0;
       for(int i = 0; i < 26; i++)
       ans = Math.max(ans, dp[node][i]);
       
       return ans;
    }
    
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s[] = br.readLine().split(" ");
		int n = Integer.parseInt(s[0]);
		int m = Integer.parseInt(s[1]);
		
		String s1 = br.readLine();
		Graph g = new Graph(n, s1);
		
		HashSet roots = new HashSet();
		for(int i = 0; i < n; i++) {
		    roots.add(i);
		}
		
		for(int M = 0; M < m; M++) {
		    String edge[] = br.readLine().split(" ");
		    int u = Integer.parseInt(edge[0]) - 1;
		    int v = Integer.parseInt(edge[1]) - 1;
		    if(roots.contains(v))
		    roots.remove(v);
		    adj[u].add(v);
		}
		
		int ans = -1;
		Iterator itr = roots.iterator();
		//System.out.println(roots);
		while(itr.hasNext()) {
		    int root = (int)itr.next();
		    
		    if(visited[root] || adj[root].size() == 0) {
		        //ans = Math.max(ans, findMax(root))
		        continue;
		    }
		    visited[root] = true;
		    checked[root] = true;
		    g.dfs(root);
		    ans = Math.max(ans, findMax(root));
		    checked[root] = false;
		}
		
		
		if(flag)
		System.out.println("-1");
		else
		System.out.println(ans);
		
	}
}


// 10 50
// ebibwbjihv
// 1 10
// 1 2
// 5 4
// 1 8
// 9 7
// 5 6
// 1 8
// 8 7
// 2 6
// 5 4
// 1 9
// 3 2
// 8 3
// 5 6
// 5 9
// 2 4
// 2 7
// 3 9
// 1 2
// 1 7
// 1 10
// 3 7
// 1 8
// 3 10
// 8 6
// 1 7
// 10 6
// 1 6
// 5 8
// 1 5
// 2 10
// 3 9
// 5 8
// 8 3
// 3 7
// 5 2
// 1 10
// 1 4
// 5 3
// 3 2
// 1 2
// 5 8
// 10 4
// 2 10
// 8 2
// 1 9
// 1 8
// 1 2
// 3 4
// 1 8
