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.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {

    static class Node implements Comparable<Node>{
        int v,indegree;
        Node(int v){
            this.v = v;
            indegree = 0;
        }

        @Override
        public int compareTo(Node node) {
            return this.v-node.v;
        }

        @Override
        public String toString(){
            return v+"";
        }
    }

    public static void main(String[] args) throws IOException {
        InputReader ir = new InputReader();
        int n = ir.readInt();
        int m = ir.readInt();
        //Make it 1-indexed
        String str = "."+ir.read();
        ArrayList<Node> graph[] = new ArrayList[n+1];
        Node nodes[] = new Node[n+1];
        for(int i=0;i<=n;i++){
            nodes[i] = new Node(i);
        }
        nodes[0].indegree = Integer.MAX_VALUE;
        int ind[] = new int[n+1];
        for(int i=0;i<graph.length;i++){
            graph[i] = new ArrayList<Node>();
        }
        while(m-->0){
            int u = ir.readInt();
            int v = ir.readInt();
            graph[u].add(nodes[v]);
            nodes[v].indegree++;
        }
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int dp[][] = new int[n+1][27];
        for(int i=1;i<=n;i++){
            if(nodes[i].indegree==0) {
                pq.add(nodes[i]);
                dp[nodes[i].v][str.charAt(nodes[i].v)-'a'+1]=1;
            }
        }
        int count=0;
        while(!pq.isEmpty()){
            Node node = pq.remove();
            count++;
            for(Node x : graph[node.v]){
                for (int i = 1; i <= 26; i++) {
//                    System.out.println("IND "+(dp[node.v][i]+(str.charAt(x.v)-'a'+1==i?1:0))+" "+dp[x.v][i]);
                    dp[x.v][i] = Math.max(dp[x.v][i],(dp[node.v][i]+(str.charAt(x.v)-'a'+1==i?1:0)));
//                    System.out.println("DP "+dp[x.v][i]);

                }
                x.indegree--;

                if (x.indegree == 0) {
                    pq.add(x);
                }
            }
        }
        if(count!=n){
            System.out.println(-1);
            return;
        }
        int ans = 1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=26;j++){
//                System.out.println(dp[i][j]+" D "+dp[nodes[i].v][j]);
                ans = Math.max(ans,dp[i][j]);
            }
        }
        System.out.println(ans);
    }

    static class InputReader {
        //This IO class belongs to Ashok Rajpurohit (@ashok1113)
        byte[] buffer = new byte[8192];
        int offset = 0;
        int bufferSize = 0;
        final InputStream in = System.in;

        public int readInt() throws IOException {
            int number = 0;
            int s = 1;
            if (offset == bufferSize) {
                offset = 0;
                bufferSize = in.read(buffer);
            }
            if (bufferSize == -1) {
                throw new IOException("No new bytes");
            }
            for (; buffer[offset] < 0x30 || buffer[offset] == '-'; ++offset) {
                if (buffer[offset] == '-') {
                    s = -1;
                }
                if (offset == bufferSize - 1) {
                    offset = -1;
                    bufferSize = in.read(buffer);
                }
            }
            for (; offset < bufferSize && buffer[offset] > 0x2f; ++offset) {
                number = (number << 3) + (number << 1) + buffer[offset] - 0x30;
                if (offset == bufferSize - 1) {
                    offset = -1;
                    bufferSize = in.read(buffer);
                }
            }
            ++offset;
            return number * s;
        }

        public int[] readIntArray(int n) throws IOException {
            int[] ar = new int[n];
            for (int i = 0; i < n; i++) {
                ar[i] = readInt();
            }

            return ar;
        }

        public int[] readIntArray1(int n) throws IOException {
            int[] ar = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                ar[i] = readInt();
            }

            return ar;
        }

        public long readLong() throws IOException {
            long res = 0;
            int s = 1;
            if (offset == bufferSize) {
                offset = 0;
                bufferSize = in.read(buffer);
            }
            for (; buffer[offset] < 0x30 || buffer[offset] == '-'; ++offset) {
                if (buffer[offset] == '-') {
                    s = -1;
                }
                if (offset == bufferSize - 1) {
                    offset = -1;
                    bufferSize = in.read(buffer);
                }
            }
            for (; offset < bufferSize && buffer[offset] > 0x2f; ++offset) {
                res = (res << 3) + (res << 1) + buffer[offset] - 0x30;
                if (offset == bufferSize - 1) {
                    offset = -1;
                    bufferSize = in.read(buffer);
                }
            }
            ++offset;
            if (s == -1) {
                res = -res;
            }
            return res;
        }

        public long[] readLongArray(int n) throws IOException {
            long[] ar = new long[n];

            for (int i = 0; i < n; i++) {
                ar[i] = readLong();
            }

            return ar;
        }

        public String read() throws IOException {
            StringBuilder sb = new StringBuilder();
            if (offset == bufferSize) {
                offset = 0;
                bufferSize = in.read(buffer);
            }

            if (bufferSize == -1 || bufferSize == 0) {
                throw new IOException("No new bytes");
            }

            for (;
                 buffer[offset] == ' ' || buffer[offset] == '\t' || buffer[offset]
                         == '\n' || buffer[offset] == '\r'; ++offset) {
                if (offset == bufferSize - 1) {
                    offset = -1;
                    bufferSize = in.read(buffer);
                }
            }
            for (; offset < bufferSize; ++offset) {
                if (buffer[offset] == ' ' || buffer[offset] == '\t'
                        || buffer[offset] == '\n' || buffer[offset] == '\r') {
                    break;
                }
                if (Character.isValidCodePoint(buffer[offset])) {
                    sb.appendCodePoint(buffer[offset]);
                }
                if (offset == bufferSize - 1) {
                    offset = -1;
                    bufferSize = in.read(buffer);
                }
            }
            return sb.toString();
        }

        public String read(int n) throws IOException {
            StringBuilder sb = new StringBuilder(n);
            if (offset == bufferSize) {
                offset = 0;
                bufferSize = in.read(buffer);
            }

            if (bufferSize == -1 || bufferSize == 0) {
                throw new IOException("No new bytes");
            }

            for (;
                 buffer[offset] == ' ' || buffer[offset] == '\t' || buffer[offset]
                         == '\n' || buffer[offset] == '\r'; ++offset) {
                if (offset == bufferSize - 1) {
                    offset = -1;
                    bufferSize = in.read(buffer);
                }
            }
            for (int i = 0; offset < bufferSize && i < n; ++offset) {
                if (buffer[offset] == ' ' || buffer[offset] == '\t'
                        || buffer[offset] == '\n' || buffer[offset] == '\r') {
                    break;
                }
                if (Character.isValidCodePoint(buffer[offset])) {
                    sb.appendCodePoint(buffer[offset]);
                }
                if (offset == bufferSize - 1) {
                    offset = -1;
                    bufferSize = in.read(buffer);
                }
            }
            return sb.toString();
        }
    }
}
