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.math.*;

public class D{
	
	static int n,m,res;
	static char a[];
	static ArrayList<Integer> e[];
	static int f[],pre[];
	static boolean dIn[],dOut[];
	static boolean dfs(int u, char c) {
		if (dIn[u]) return false;
		dIn[u]=true;
		int i,v;
		for (i=0;i<e[u].size();i++) {
			v=e[u].get(i);
			if (dIn[v]==true) {
				if (dOut[v]==false) {
					f[u]=-1;
					return true;
				}
				else {
					f[u]=Math.max(f[u], f[v]);
				}
			}else {
				if (dfs(v,c)==true)
					return true;
				f[u]=Math.max(f[u], f[v]);
			}
		}
		dOut[u]=true;
		if (a[u]==c) f[u]++;
		return false;
	}
	static void process() {
		f=new int[n+2]; 
		dIn=new boolean[n+2];dOut=new boolean[n+2];
		res=0;
		char c; int u;
		for (c='a';c<='z';c++) {
			Arrays.fill(f, 0);
			Arrays.fill(dIn,false);
			Arrays.fill(dOut,false);
			for (u=1;u<=n;u++)
				if (a[u]==c) {
					if (dIn[u]==false) {
						if (dfs(u,c)==true) { 
							res=-1;
							return;
						}
					}
					res=Math.max(res, f[u]);
				}
		}
	}
	static void MainMethod()throws Exception{
		n=reader.nextInt();
		m=reader.nextInt();
		a=(" "+reader.next()).toCharArray();
		e=new ArrayList[n+2];
		int i,j,u,v;
		for (i=0;i<e.length;i++) {
			e[i]=new ArrayList<Integer>();
			e[i].clear();
		}
		for (i=0;i<m;i++) {
			u=reader.nextInt();
			v=reader.nextInt();
			e[u].add(v);
		}
		process();
		printer.print(res);
	}
	public static void main(String[] args)throws Exception{
		MainMethod();
		printer.close();
	}
	static void halt(){
		printer.close();
		System.exit(0);
	}
	static PrintWriter printer=new PrintWriter(new OutputStreamWriter(System.out));
	static class reader{
		static BufferedReader bReader=new BufferedReader(new InputStreamReader(System.in));
		static StringTokenizer token=new StringTokenizer("");
		static String readNextLine() throws Exception{
			return bReader.readLine();
		}
		static String next() throws Exception{
			while (token.hasMoreTokens()==false){
				token=new StringTokenizer(bReader.readLine());
			}
			return token.nextToken();
		}
		static int nextInt()throws Exception{
			while (token.hasMoreTokens()==false){
				token=new StringTokenizer(bReader.readLine());
			}
			return Integer.parseInt(token.nextToken());
		}
		static long nextLong()throws Exception{
			while (token.hasMoreTokens()==false){
				token=new StringTokenizer(bReader.readLine());
			}
			return Long.parseLong(token.nextToken());
		}
		static double nextDouble()throws Exception{
			while (token.hasMoreTokens()==false){
				token=new StringTokenizer(bReader.readLine());
			}
			return Double.parseDouble(token.nextToken());
		}
	}
	static class MyMathCompute{
		static long [][] MatrixMultiplyMatrix(long [][] A, long [][] B, long mod) throws Exception{
			int n=A.length, m=B[0].length; 
			int p=A[0].length;
			int i,j,k;
			if (B.length!=p) throw new Exception("invalid matrix input");
			long [][] res=new long [n][m];
			for (i=0;i<n;i++) for (j=0;j<m;j++){
				if (A[i].length!=p) throw new Exception("invalid matrix input");
				res[i][j]=0;
				for (k=0;k<p;k++)
					res[i][j]=(res[i][j]+((A[i][k]*B[k][j])% mod))% mod;
			}
			return res;
		}
		static double [][] MatrixMultiplyMatrix(double [][] A, double [][] B ) throws Exception{
			int n=A.length, m=B[0].length; 
			int p=A[0].length;
			int i,j,k;
			if (B.length!=p) throw new Exception("invalid matrix input");
			double [][] res=new double [n][m];
			for (i=0;i<n;i++) for (j=0;j<m;j++){
				if (A[i].length!=p) throw new Exception("invalid matrix input");
				res[i][j]=0;
				for (k=0;k<p;k++)
					res[i][j]=res[i][j]+(A[i][k]*B[k][j]);
			}
			return res;
		}
		static long [][] MatrixPow(long [][] A,long n, long mod) throws Exception{
			if (n==1) return A;
			long [][] res=MatrixPow(A, n/2, mod);
			res=MatrixMultiplyMatrix(res, res, mod);
			if ((n % 2) == 1) res=MatrixMultiplyMatrix(A,res, mod);		
			return res;
		}
		static double [][] MatrixPow(double [][] A,long n) throws Exception{
			if (n==1) return A;
			double[][] res=MatrixPow(A, n/2);
			res=MatrixMultiplyMatrix(res, res);
			if ((n % 2) == 1) res=MatrixMultiplyMatrix(A,res);		
			return res;
		}
		static long pow(long a,long n,long mod){
			a= a % mod;
			if (n==0) return 1;
			long k=pow(a,n/2,mod);
			if ((n % 2)==0) return ((k*k)%mod);
			else return (((k*k) % mod)*a) % mod;
		}
		static double pow(double a,long n){
			if (n==0) return 1;
			double k=pow(a,n/2);
			if ((n % 2)==0) return (k*k);
			else return (((k*k) )*a) ;
		}
	}
}
