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.lang.*;
import java.lang.reflect.Array;
import java.io.*;
import java.math.*;
import java.text.DecimalFormat;
public class Prac{     
    static class InputReader { 
        private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;
 	public InputReader(InputStream st) {
            this.stream = st;
	} 
	public int read() {
            if (snumChars == -1)
	 	throw new InputMismatchException();
            if (curChar >= snumChars) {
		curChar = 0;
                try {
                    snumChars = stream.read(buf);
		} 
                catch (IOException e) {
                    throw new InputMismatchException();
           	}
		if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
	}
        public int ni() {
            int c = read();
            while (isSpaceChar(c)) {
               	c = read();
            }
            int sgn = 1;
            if (c == '-') {
		sgn = -1;
		c = read();
            }
            int res = 0;
            do {
		res *= 10;
		res += c - '0';
		c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
	} 
	public long nl() {
            int c = read();
            while (isSpaceChar(c)) {
            c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
	} 
	public int[] nia(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
		a[i] = ni();
            }
            return a;
	} 
	public String rs() {
            int c = read();
            while (isSpaceChar(c)) {
		c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
		res.appendCodePoint(c);
                    c = read();
            } while (!isSpaceChar(c));
            return res.toString();
	}
	public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
		c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        } 
	public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}
 
	private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
	} 
    }
    static PrintWriter w = new PrintWriter(System.out);
    static Set<Integer> g;
    static Set<Integer> b;
    static boolean f,v[];
    static ArrayList<Integer> arr[];
    static int ans[][];
    static int c[],max=Integer.MIN_VALUE;
    static int[] cycle(int i,int cA[]){
        if(g.contains(i)){
            f=true;
            return cA;
        }
        if(b.contains(i)){
//            for(int i1=0;i1<26;i1++){
//                max=Math.max(max,cA[i1]+ans[i][i1]);
//            }
            return ans[i];
        }
        v[i]=true;
        g.add(i);
        //cA[c[i]]++;
        Iterator itr=arr[i].iterator();
        //int ans[]=new int[26];
        int res[]=new int[26];
        //cA[c[i]]++;
        while(itr.hasNext()){
            int a=(int)itr.next();
//            int ar[]=cycle(a);
//            for(int i1=0;i1<26;i1++){
//                ans[i][i1]=Math.max(ans[i][i1],ar[i1]);
//            }
             int ar[]=cycle(a,cA);
             for(int i1=0;i1<26;i1++){
                 res[i1]=Math.max(ar[i1],res[i1]);
             }
        }
        
        res[c[i]]++;
        //cA[c[i]]++;
//        for(int i1=0;i1<26;i1++){
//            max=Math.max(cA[i1],max);
//        }
//        ans[i]=cA;
//        cA[c[i]]--;
        g.remove(i);
        b.add(i);
        for(int j=0;j<26;j++){
            ans[i][j]=res[j];
        }
        res[c[i]]--;
        return ans[i];
    }
    public static void main(String[] args) throws IOException {   
        InputReader sc=new InputReader(System.in);
        int n=sc.ni();
        int m=sc.ni();
        c=new int[n+1];
        v=new boolean[n+1];
        g=new HashSet<Integer>();
        b=new HashSet<Integer>();
        arr=new ArrayList[n+1];
        ans=new int[n+1][26];
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        //cA=new int[26];
        f=false;
        //ans=new int[n+1];
        for(int i=0;i<=n;i++){
            arr[i]=new ArrayList<Integer>();
        }
        String s=sc.nextLine();
        for(int i=0;i<n;i++){
            c[i+1]=s.charAt(i)-'a';
        }
        for(int i=0;i<m;i++){
            int u=sc.ni();
            int v=sc.ni();
            arr[u].add(v);
        }
        int res[]=new int[26];
        for(int i=1;i<=n;i++){
            if(!v[i]){
                int ar[]=cycle(i,new int[26]);

                for(int j=0;j<26;j++){
                    res[j]=Math.max(res[j],ar[j]);
                    max=Math.max(res[j],max);
                }
            }
        }
        
        w.println((f)?-1:max);
        w.close();
    }
}

