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 Template {

	static int mod = 1000000007;

	static int[][] dp = new int[(int)(3*1e5)+10][26]; 
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		int yo = 1;
		while (yo-- > 0) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			String a = sc.next();
			ArrayList<ArrayList<Integer>> list = new ArrayList<>();
			for(int i = 0; i < n; i++) {
				list.add(new ArrayList<>());
			}
			
			for(int i = 0; i < m; i++) {
				int x = sc.nextInt()-1;
				int y = sc.nextInt()-1;
				list.get(x).add(y);
			}
			
			int[] arr = topoSort(n,list);
			// if cyclic the return -1;
			if(isCyclic) {
				out.println(-1);
				continue;
			}
			
			
			int ans = 1;
	        for(int i = arr.length-1; i >= 0; i--){
	            int node = arr[i];
	            dp[node][a.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] + (a.charAt(node) == (char)c+'a' ? 1 : 0));
	                    ans = Math.max(ans,dp[node][c]);
	                }
	            }
	        }
	        
	        out.println(ans);
			
		}
		out.close();
	}
	
	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 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);
}
