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 test {
    static boolean DEBUG_FLAG = false;
    int INF = (int)1e9;
    long MOD = 1000000007;
    
    static void debug(String s) {
        if(DEBUG_FLAG) {
            System.out.print(s);
        }
    }
    
    int n, m;
    char[] s;
    List<Integer>[] adj;
    
    ArrayList<Integer> toposort() {
        ArrayList<Integer> ord = new ArrayList<>();
        int[] deg = new int[n];
        for(int i=0; i<n; i++) {
            for(int j=0; j<adj[i].size(); j++) {
                deg[adj[i].get(j)]++;
            }
        }
        for(int i=0; i<n; i++) {
            if(deg[i]==0) {
                ord.add(i);
            }
        }
        for(int i=0; i<ord.size(); i++) {
            int v = ord.get(i);
            for(int j=0; j<adj[v].size(); j++) {
                int x= adj[v].get(j);
                deg[x]--;
                if(deg[x]==0) ord.add(x);
            }
        }
        for(int i=0; i<n; i++) {
            if(deg[i]>0) return null;
        }
        return ord;
    }
    
    void solve(InputReader in, PrintWriter out) throws IOException {
        n = in.nextInt();
        m = in.nextInt();
        s = in.next().toCharArray();
        adj = new ArrayList[n];
        for(int i=0; i<n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for(int i=0; i<m; i++) {
            int x = in.nextInt()-1;
            int y = in.nextInt()-1;
            adj[x].add(y);
        }
        ArrayList<Integer> ord = toposort();
        if(ord==null) {
            out.println(-1);
            return;
        }
        int[][] dp = new int[n][26];
        int max = -1;
        for(int i=ord.size()-1; i>=0; i--) {
            int v = ord.get(i);
            dp[v][s[v]-'a'] = 1;
            for(int j=0; j<adj[v].size(); j++) {
                int u = adj[v].get(j);
//                out.println("edge: "+v+" -> "+u);
                for(int k=0; k<26; k++) {
                    int x = 0;
                    if(k==s[v]-'a') x++;
                    dp[v][k] = Math.max(dp[v][k], dp[u][k]+x);
                    max = Math.max(dp[v][k], max);
                }
            }
        }
        out.println(max);
    }
    
    
    public static void main(String[] args) throws IOException {
        if(args.length>0 && args[0].equalsIgnoreCase("d")) {
            DEBUG_FLAG = true;
        }
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        int t = 1;//in.nextInt();
        long start = System.nanoTime();
        while(t-- >0) {
            new test().solve(in, out);
        }
        long end = System.nanoTime();
        debug("\nTime: " + (end-start)/1e6 + " \n\n");
        out.close();
    }
    
    static class InputReader {
        static BufferedReader br;
        static StringTokenizer st;
    
        public InputReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                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());
        }
    }
}