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.*;
import java.util.*;

public class fre {

	static int mod = 1000000007;

	static int[][] dp = new int[(int)(3*1e5)+10][26]; 
	static int ans;
    static boolean isCyclic = false;

    static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) {
        int[] degree = new int[V];
        for(int i = 0; i < V; i++){
            for(int e : adj.get(i)){
                degree[e]++;
            }
        }
        
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < V; i++){
            if(degree[i] == 0){
                q.add(i);
            }
        }
        
        int count = 0;
        int[] ans = new int[V];
        int index = 0;
        while(!q.isEmpty()){
            int curr = q.poll();
            count++;
            ans[index++] = curr;
            for(int neighbour : adj.get(curr)){
                degree[neighbour]--;
                if(degree[neighbour] == 0){
                    q.add(neighbour);
                }
            }
        }
        if(count != V) {
        	isCyclic = true; 
        }
        return ans;
    }


    static int beauty(int n, int m, String s, int x[], int y[])
    {
        ans = 0;
        
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			list.add(new ArrayList<>());
		}

        for(int i = 0; i < m; i++) {

			list.get(x[i]).add(y[i]);
		}

        int[] arr = topoSort(n,list);

        if(isCyclic==true) {
			return -1;
		}

        int ans = 1;
        for(int i = arr.length-1; i >= 0; i--){
            int node = arr[i];
            dp[node][s.charAt(node)-'a'] = 1;
            for(int e : list.get(node)){
                for(int c = 0; c < 26; c++){
                    dp[node][c] = Math.max(dp[node][c], dp[e][c] + (s.charAt(node) == (char)c+'a' ? 1 : 0));
                    ans = Math.max(ans,dp[node][c]);
                }
            }
        }
        return ans;
    }
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		
		String[] inp = br.readLine().split(" ");
		int n = Integer.parseInt(inp[0]);
		int m = Integer.parseInt(inp[1]);
		String s = br.readLine();
		
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			list.add(new ArrayList<>());
		}
        int x[] = new int[m];
        int y[]=new int[m];
		
		for(int i = 0; i < m; i++) {
			inp = br.readLine().split(" ");


			 x[i] = Integer.parseInt(inp[0])-1;
			 y[i] = Integer.parseInt(inp[1])-1;
			list.get(x[i]).add(y[i]);
		}
		
		 int res = beauty(n,m,s,x,y);
        System.out.println(res);
		
		return ;
	}
	
	

	// static class Pair {
	// 	int x;
	// 	int y;

	// 	public Pair(int x, int y) {
	// 		this.x = x;
	// 		this.y = y;
	// 	}
	// }

	// static void ruffleSort(int[] a) {
	// 	int n = a.length;
	// 	Random r = new Random();
	// 	for (int i = 0; i < a.length; i++) {
	// 		int oi = r.nextInt(n), temp = a[i];
	// 		a[i] = a[oi];
	// 		a[oi] = temp;
	//	}
	//	Arrays.sort(a);
	//}

	// static long gcd(long a, long b) {
	// 	if (b == 0)
	// 		return a;
	// 	return gcd(b, a % b);
	// }

	// static boolean[] sieve(int N) {
	// 	boolean[] sieve = new boolean[N];
	// 	for (int i = 2; i < N; i++)
	// 		sieve[i] = true;

	// 	for (int i = 2; i < N; i++) {
	// 		if (sieve[i]) {
	// 			if (i * i < 0)
	// 				continue;
	// 			for (int j = i * i; j < N; j += i) {
	// 				sieve[j] = false;
	// 			}
	// 		}
	// 	}
	// 	return sieve;
	// }

	// static long pow(int a, long b) {
	// 	if (b == 0) {
	// 		return 1;
	// 	}
	// 	if (b == 1) {
	// 		return a;
	// 	}
	// 	if (b % 2 == 0) {
	// 		long ans = pow(a, b / 2);
	// 		return ans * ans;
	// 	} else {
	// 		long ans = pow(a, (b - 1) / 2);
	// 		return a * ans * ans;
	// 	}

	// }

	// static class FastScanner {
	// 	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	// 	StringTokenizer st = new StringTokenizer("");

	// 	String next() {
	// 		while (!st.hasMoreTokens())
	// 			try {
	// 				st = new StringTokenizer(br.readLine());
	// 			} catch (IOException e) {
	// 				e.printStackTrace();
	// 			}
	// 		return st.nextToken();
	// 	}

	// 	int nextInt() {
	// 		return Integer.parseInt(next());
	// 	}

	// 	int[] readArray(int n) {
	// 		int[] a = new int[n];
	// 		for (int i = 0; i < n; i++)
	// 			a[i] = nextInt();
	// 		return a;
	// 	}

	// 	long nextLong() {
	// 		return Long.parseLong(next());
	// 	}
	// }

	//	For Input.txt and Output.txt	
	//	FileInputStream in = new FileInputStream("input.txt");
	//	FileOutputStream out = new FileOutputStream("output.txt");
	//	PrintWriter pw = new PrintWriter(out);
	//	Scanner sc = new Scanner(in);
}