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.*;
import java.util.concurrent.TimeUnit;
 
public class substring2 {
	static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	
	static List<Set<Integer>> adjList = new ArrayList<>();
	static List<Set<Integer>> revList = new ArrayList<>();
	static StringBuilder nodeMap;
	
	static int[][] dp;
	static boolean[] visited;
	
	public static void main (String [] args) throws Exception {
	    BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
 
	    StringTokenizer st = new StringTokenizer(f.readLine());
	    int N = Integer.parseInt(st.nextToken())+1;
	    int M = Integer.parseInt(st.nextToken());
	    
	    nodeMap = new StringBuilder(f.readLine());
	    for(int i = 0; i < nodeMap.length()+1; i++) {
	    	adjList.add(new HashSet<>());
	    	revList.add(new HashSet<>());
	    }
	    
	    for(int m = 0; m < M; m++) {
	    	st = new StringTokenizer(f.readLine());
	    	int n1 = Integer.parseInt(st.nextToken());
	    	int n2 = Integer.parseInt(st.nextToken());
	    	adjList.get(n1).add(n2);
	    	revList.get(n2).add(n1);
	    }
	    dp = new int[N][26];
	    visited = new boolean[N];
	    
	    
	    Queue<Integer> queue = new LinkedList<>();
	    for(int i = 1; i < adjList.size(); i++) {
	    	if(revList.get(i).size() == 0) {
	    		queue.add(i);
	    	}
	    }
	    
	    while(queue.size() > 0) {
	    	int i = queue.poll();
	    	//System.out.println(i);
	    	visited[i] = true;
			dp[i][nodeMap.charAt(i-1)-97]++;
	    	for(int each: adjList.get(i)) {
	    		dfs(each, i);
	    		revList.get(each).remove(i);
	    		if(revList.get(each).size() == 0) {
	    			queue.add(each);
	    		}
	    	}
	    }
	    
	    //for(int[] each : dp) {
	    //	System.out.println(Arrays.toString(each));
	    //}
	    
	    for(int i = 1; i < visited.length; i++) {
	    	if(!visited[i]) {
	    		out.println(-1);
	    		out.close();
	    		System.exit(0);
	    	}
	    }
	    
	    //for(int[] each: dp)
	    //	System.out.println(Arrays.toString(each));
	    
	    int max = 0;
	    for(int i = 0; i < N; i++) {
	    	for(int j = 0; j < 26; j++) {
	    		max = Math.max(max, dp[i][j]);
	    	}
	    }
	    
	    out.println(max);
	    
	    out.close();
	    f.close();
	}
	
	public static void dfs(int node, int parent) {
		visited[node] = true;
		for(int i = 0; i < 26; i++) {
			dp[node][i] = Math.max(dp[node][i], dp[parent][i]);
		}
	}
	
}