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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @author Don Li
 */
public class Substring {
    
    int N = (int) 3e5 + 10;
    
    int[][] G;
    
    int ptr = 0;
    int[] sta = new int[N];
    int[] ord = new int[N];
    
    void solve() {
        int n = in.nextInt(), m = in.nextInt();
        char[] s = in.nextToken().toCharArray();
        int[] fr = new int[m], to = new int[m];
        for (int i = 0; i < m; i++) {
            fr[i] = in.nextInt() - 1;
            to[i] = in.nextInt() - 1;
        }
        G = build_graph(n, fr, to);
        
        for (int i = 0; i < n; i++) {
            if (sta[i] == 0) {
                if (!dfs(i)) {
                    out.println(-1);
                    return;
                }
            }
        }
        
        int[][] dp = new int[N][26];
        for (int i = 0; i < n; i++) {
            int u = ord[i];
            for (int v : G[u]) {
                for (int j = 0; j < 26; j++) {
                    dp[u][j] = Math.max(dp[u][j], dp[v][j]);
                }
            }
            dp[u][s[u] - 'a']++;
        }
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 26; j++) {
                ans = Math.max(ans, dp[i][j]);
            }
        }
        out.println(ans);
    }
    
    boolean dfs(int u) {
        sta[u] = 1;
        for (int v : G[u]) {
            if (sta[v] == 0) {
                if (!dfs(v)) return false;
            } else if (sta[v] == 1) {
                return false;
            }
        }
        ord[ptr++] = u;
        sta[u] = 2;
        return true;
    }
    
    int[][] build_graph(int n, int[] from, int[] to) {
        int[][] G = new int[n][];
        int[] cnt = new int[n];
        for (int i = 0; i < from.length; i++) {
            cnt[from[i]]++;
        }
        for (int i = 0; i < n; i++) G[i] = new int[cnt[i]];
        for (int i = 0; i < from.length; i++) {
            G[from[i]][--cnt[from[i]]] = to[i];
        }
        return G;
    }
    
    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new Substring().solve();
        out.close();
    }
    
    static FastScanner in;
    static PrintWriter out;
    
    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;
        
        public FastScanner(BufferedReader in) {
            this.in = in;
        }
        
        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        
        public long nextLong() {
            return Long.parseLong(nextToken());
        }
        
        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}
