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.io.*;
//import java.lang.*;
 
//only first 100 lines are relevant
//don't forget to invert the fileread bit when executing on console
public  class Main{
 

    public static boolean[] safe;
	public static int[][] memo;
	public static int cnt,ans;
    public static final long bil = (long)1e9+7;
    public static int fileread = 0; 
    
    public static void main(String ...arg) throws IOException
    {
        /*console writer*/
        // cout = new PrintWriter(new BufferedOutputStream(System.out));
        // /*Debug Reader*/
        // //Scan cin =new Scan();
        // if(fileread == 1)
        // {
        //     try
        //     {
        //     cin = new Read(new FileInputStream(new File("in3.txt")));
        //     //cin = new InputReader(new FileInputStream(new File("in1.txt")));
        //     }
        //     catch (IOException error){}
        // }
        // else{
        //     cin = new Read(System.in);
        //     //cin = new InputReader(System.in);
        // }
        
 Scanner sc=new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		String s = "@"+sc.next();
		
 
		//creating the graph
		ArrayList<Integer>[] graph = new ArrayList[n+1];
		for(int i=0;i<=n;i++) graph[i] = new ArrayList<Integer>();
		int[] indegree = new int[n+1];
		for(int i=0;i<m;i++)
		{
			int a = sc.nextInt();
			int b = sc.nextInt();
			graph[a].add(b);
			indegree[b]++;
		}
		//creting the dp
		memo = new int[n+1][26];
		cnt = 0;
		ans = Integer.MIN_VALUE;
		toposort(graph,indegree,s);
		if(cnt!=n)
			System.out.println(-1);
		else
			System.out.print(ans);
	//	cout.close();
    }
 
	public static void toposort(ArrayList<Integer>[] graph,int[] indegree,String s)
	{
		Queue<Integer> q = new LinkedList<>();
		for(int i=1;i<indegree.length;i++)
		{
			if(indegree[i] == 0)
			{q.add(i); memo[i][alpha(s.charAt(i))]=1;} 
		}
		while(!q.isEmpty())
		{
			int node =  q.peek();
			cnt++;
			q.remove();
			for(int child:graph[node])
			{
				for(int j=0;j<26;j++)
				{
					memo[child][j] = Math.max(memo[child][j],memo[node][j]+(j==alpha(s.charAt(child))?1:0 ));	
					ans = Math.max(memo[child][j],ans);
				}
				indegree[child]--;
				if(indegree[child] == 0)
					q.add(child);
			}
		}
	}
 
	public static int alpha(char c)
	{
		return Character.toUpperCase(c) - 65;
	}
 
}