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.
// Don't place your source in a package
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
import java.util.stream.Stream;


// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

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

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(System.out);

        int T=1;
        for(int t=0;t<T;t++){
            int n=Int();int m=Int();
            String s=Str();
            int A[][]=new int[m][2];

            for(int i=0;i<m;i++){
                A[i][0]=Int()-1;
                A[i][1]=Int()-1;
            }

            Solution sol=new Solution(out);
            sol.solution(s,A);
        }
        out.flush();

    }


    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}






class Solution{
    PrintWriter out;
    public Solution(PrintWriter out){
        this.out=out;
    }


    boolean good=true;
    boolean visit[];
    Map<Integer,Set<Integer>>f=new HashMap<>();
    public void solution(String s,int B[][]){
        char A[]=s.toCharArray();
        int n=A.length;
        int res=0;

        int dp[][]=new int[n][26];
        int in[]=new int[n];
        visit=new boolean[n];



        for(int p[]:B){
            int u=p[0],v=p[1];
            if(!f.containsKey(u)){
                f.put(u,new HashSet<>());
            }
            if(!f.containsKey(v)){
                f.put(v,new HashSet<>());
            }

            if(!f.get(u).contains(v)){
                in[v]++;
                f.get(u).add(v);
            }

        }
        
        for(int i=0;i<n;i++){
            if(!f.containsKey(i)){
                f.put(i,new HashSet<>());
            }
        }



        for(int i=0;i<n;i++){
            if(!visit[i]){
                visit[i]=true;
                Set<Integer>stack=new HashSet<>();
                stack.add(i);
                dfs(i,stack);
                if(!good){
                    out.println(-1);
                    return;
                }
            }
        }



        Queue<Integer>q=new LinkedList<>();
        for(int i=0;i<in.length;i++){
            if(in[i]==0){
                dp[i][A[i]-'a']=1;
                q.add(i);
            }
        }



        while(q.size()!=0){
            int root=q.poll();
            for(int next:f.get(root)){
                for(int j=0;j<26;j++){
                    dp[next][j]=Math.max(dp[next][j],dp[root][j]);
                }
                in[next]--;
                if(in[next]==0){
                    q.add(next);
                    dp[next][A[next]-'a']++;
                }
            }
        }




        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                res=Math.max(res,dp[i][j]);
            }
        }
        out.println(res);
    }

    public void dfs(int cur,Set<Integer>stack){
        for(int next:f.get(cur)){
            if(visit[next]){
                if(stack.contains(next)){
                    good=false;
                }
            }
            else{
                visit[next]=true;
                stack.add(next);
                dfs(next,stack);
                stack.remove(next);
            }
        }
    }


}



/*
                             ;\
                            |' \
         _                  ; : ;
        / `-.              /: : |
       |  ,-.`-.          ,': : |
       \  :  `. `.       ,'-. : |
        \ ;    ;  `-.__,'    `-.|
         \ ;   ;  :::  ,::'`:.  `.
          \ `-. :  `    :.    `.  \
           \   \    ,   ;   ,:    (\
            \   :., :.    ,'o)): ` `-.
           ,/,' ;' ,::"'`.`---'   `.  `-._
         ,/  :  ; '"      `;'          ,--`.
        ;/   :; ;             ,:'     (   ,:)
          ,.,:.    ; ,:.,  ,-._ `.     \""'/
          '::'     `:'`  ,'(  \`._____.-'"'
             ;,   ;  `.  `. `._`-.  \\
             ;:.  ;:       `-._`-.\  \`.
              '`:. :        |' `. `\  ) \
      -hrr-      ` ;:       |    `--\__,'
                   '`      ,'
                        ,-'


                      free bug dog
*/





