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 CF919_D2_D {
	
	
	
	public static void main(String[] args)throws Throwable {
		MyScanner sc=new MyScanner();
		PrintWriter pw=new PrintWriter(System.out);
		
		n=sc.nextInt();
		int m=sc.nextInt();
		a=sc.next().toCharArray();
		adj=new int [n][];
		int [] deg=new int [n];
		int [] u=new int [m];
		int [] v=new int [m];
		for(int i=0;i<m;i++){
			u[i]=sc.nextInt()-1;
			v[i]=sc.nextInt()-1;
			if(u[i]==v[i]){
				System.out.println(-1);
				return;
			}
			deg[u[i]]++;
		}
		for(int i=0;i<n;i++)
			adj[i]=new int[deg[i]];
		Arrays.fill(deg, 0);
		for(int i=0;i<m;i++)
			adj[u[i]][deg[u[i]]++]=v[i];
		ok=true;
		status=new int [n];
		parent=new int [n];
		for(int i=0;i<n;i++)
			if(status[i]==UNVISITED){
				edgeType(i);
				if(!ok)
					break;
			}
		if(!ok)
			pw.println(-1);
		else{
			cnt=new int [n];
			int ans=0;
			for(cur='a';cur<='z';cur++){
				Arrays.fill(cnt, -1);
				int max=0;
				for(int i=0;i<n;i++)
					max=Math.max(max, dfs(i));
				ans=Math.max(ans, max);
			}
			pw.println(ans);
		}
		
		
		pw.flush();
		pw.close();
	}
	
	static int n;
	static char cur;
	static int [] cnt;
	
	static int dfs(int u){
		if(cnt[u]!=-1)
			return cnt[u];
		int ans=0;
		for(int v : adj[u])
			ans=Math.max(ans, dfs(v));
		if(a[u]==cur)
			ans++;
		return cnt[u]=ans;
	}
	static final int VISITED = 2, EXPLORED = 1, UNVISITED = 0;
	static boolean ok;
	static char [] a;
	static int [][] adj;
	static int[] parent, status;
	static void edgeType(int u)
	{
		status[u] = EXPLORED;
		for(int v: adj[u])
			if(status[v] == UNVISITED)
			{
				parent[v] = u;
				edgeType(v);
			}
			else
				if(status[v] != VISITED && v!=parent[u]){
					ok=false;
					return;
				}
		status[u] = VISITED;
	}
	
	static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {while (st == null || !st.hasMoreElements()) {
			try {st = new StringTokenizer(br.readLine());}
			catch (IOException e) {e.printStackTrace();}}
		return st.nextToken();}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());}
		double nextDouble() {return Double.parseDouble(next());}
		String nextLine(){String str = "";
		try {str = br.readLine();}
		catch (IOException e) {e.printStackTrace();}
		return str;}
	}
} 