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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

public class Substring {

	public static void main(String[] args) throws IOException {
   BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   String []sl=br.readLine().split(" ");
   int n=Integer.parseInt(sl[0]);
   int m=Integer.parseInt(sl[1]);
   ArrayList<ArrayList<Integer>> graph=new ArrayList<>();
   String s=br.readLine();
   for(int i=0;i<n;i++){
	   graph.add(new ArrayList<>());
   }
   int []deg=new int[n];
   for(int  i=0;i<m;i++){
	   String []sm=br.readLine().split(" ");
	   int a=Integer.parseInt(sm[0]);
	   int b=Integer.parseInt(sm[1]);
	   graph.get(a-1).add(b-1);
	   
	   deg[b-1]++;
   }
   LinkedList<Integer> queue=new LinkedList<>();
   int [][]f=new int[n][26];
   for(int i=0;i<n;i++){
	   if(deg[i]==0){
		   f[i][s.charAt(i)-'a']++;
		   queue.addLast(i);
	   }
   }
  
   int rem=n;
   while(queue.size()>0){
	   int val=queue.removeFirst();
	   rem--;
	   for(int nbr:graph.get(val)){
		   for(int j=0;j<26;j++){
			   f[nbr][j]=Math.max(f[nbr][j], f[val][j]+(s.charAt(nbr)-'a'==j?1:0));
		   }
		     deg[nbr]--;
		     if(deg[nbr]==0){
		    	 queue.addLast(nbr);
		     }
	   }
   }
		if(rem>0){
			System.out.println(-1);
		}else{
			int max=0;
			for(int i=0;i<n;i++){
				for(int j=0;j<26;j++){
					max=Math.max(f[i][j], max);
				}
			}System.out.println(max);
		}
		
	}

}
