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.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;

public class d {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int m = in.nextInt();
		
		ArrayList<TreeSet<Integer>> adj = new ArrayList<>();
		int[] incoming = new int[n];
		char[] l = in.next().toCharArray();
		
		for(int i=0; i<n; i++)
			adj.add(new TreeSet<Integer>());
		
		for(int i=0; i<m; i++){
			int a = in.nextInt()-1;
			int b = in.nextInt()-1;
			
			if(!adj.get(a).contains(b)){
				adj.get(a).add(b);
				incoming[b]++;
			}
		}
		
		int[][] dp = new int[n][26];
		for(int i=0; i<n; i++)
			dp[i][l[i]-'a'] = 1;
		
		int best = Integer.MIN_VALUE;
		boolean[] visited = new boolean[n];
		
		
		ArrayDeque<Integer> que = new ArrayDeque<Integer>();
		
		for(int i=0; i<n; i++)
			if(incoming[i] == 0) que.add(i);
		
		while(!que.isEmpty()){
			int cur = que.poll();
			
			visited[cur] = true;
			
			Iterator<Integer> i = adj.get(cur).iterator();
			while(i.hasNext()){
				int next = i.next();
				incoming[next]--;
				
				for(int j=0; j<26; j++){
					dp[next][j] = Math.max(dp[next][j], dp[cur][j] + ((j == (l[next]-'a')) ? 1 : 0));
					best = Math.max(best, dp[next][j]);
				}
				
				if(incoming[next] == 0)
					que.add(next);
			}
		}
		
//		for(int i=0; i<n; i++){
//			for(int j=0; j<26; j++)
//				System.out.print(dp[i][j]+" ");
//			System.out.println();
//		}
		boolean cycle = false;
		for(int i=0; i<n; i++){
			if(!visited[i]){
				cycle = true;
			}
		}
		
		if(!cycle) System.out.println(best);
		else System.out.println(-1);
	}
}

/*
7 6
ababccc
1 2
1 4
2 4
2 3
5 6
6 7

7 7
ababccc
1 2
1 4
2 4
2 3
5 6
6 7
7 5
 
5 4
aabcd
1 2
1 3
4 2
4 5

7 8
aabccec
1 2
1 3
4 2
4 5
2 6
5 6
6 7
5 7

6 7
aaaade
1 2
1 3
4 2
4 5
2 5
5 6
6 3

3 5
aba
1 2
1 3
1 3
2 3
2 3


*/