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.DataInputStream;
import java.io.IOException;
import java.util.Vector;

public class Task919D {

    public static class FastScanner {

        protected static final int STRBUFFERLENGTH = 0x1000;

        protected DataInputStream dataInputStream;
        protected byte[] buffer = new byte[0x10000];
        protected byte[] strbuffer = new byte[STRBUFFERLENGTH];
        protected int bufferOffset;
        protected int bufferLength;
        protected boolean isEndOfFile;

        public FastScanner() throws IOException {
            dataInputStream = new DataInputStream(System.in);
            Read();
        }

        protected void Read() throws IOException {
            final int length = dataInputStream.read(buffer);
            if (length > 0) {
                bufferLength = length;
            } else {
                bufferLength = 0;
                isEndOfFile = true;
            }
            bufferOffset = 0;
        }

        protected byte nextByte() throws IOException {
            if (bufferOffset == bufferLength) {
                if (!isEndOfFile) Read();
                if (isEndOfFile) return 0;
            }
            return buffer[bufferOffset++];
        }

        public int nextInt() throws IOException {
            int a = 0;
            boolean isNegative = false;

            byte b = nextByte();
            while (b <= ' ') b = nextByte();
            if (b == '-') {
                isNegative = true;
                b = nextByte();
            }
            while (b > ' ') {
                a = a * 10 + (b - '0');
                b = nextByte();
            }
            return isNegative ? -a : a;
        }

        public String nextLine() throws IOException {
            String s = "";
            int strbufferOffset = 0;

            byte b = nextByte();
            while (b <= ' ') b = nextByte();

            do {
                strbuffer[strbufferOffset++] = b;
                if (strbufferOffset >= STRBUFFERLENGTH) {
                    s += new String(strbuffer, 0, STRBUFFERLENGTH);
                    strbufferOffset = 0;
                }
                b = nextByte();
            } while (b != '\n' && b != '\r' && b != 0);
            s += new String(strbuffer, 0, strbufferOffset);

            return s;
        }

    }

    public static final int INFINITY = -1;
    public static final int OK = 0;
    public static final int LETTERS = 26;

    public static class Node {
        public char letter;
        public Vector<Branch> branches = new Vector<Branch>();
        public boolean marked = false;
        public boolean calculated = false;

        public Node(final char letter) {
            this.letter = letter;
        }
    }

    public static class Branch {
        public int toNode;

        public Branch(final int toNode) {
            this.toNode = toNode;
        }
    }

    public static class Graf {
        public Node[] nodes;
        public int[][] maxPaths;

        public Graf(final int n) {
            nodes = new Node[n];
            maxPaths = new int[n][LETTERS];
        }

        public int GetMaxPath() {
            for (int i = 0; i < nodes.length; i++) {
                if (FillMaxPath(i) == INFINITY) return INFINITY;
            }
            int maxPath = 0;
            for (int i = 0; i < nodes.length; i++) for (int j = 0; j < LETTERS; j++) {
                maxPath = Math.max(maxPath, maxPaths[i][j]);
            }
            return maxPath;
        }

        public int FillMaxPath(final int fromNode) {
            final Node node = nodes[fromNode];
            if (node.marked) {
                return INFINITY;
            } else if (node.calculated) {
                return OK;
            } else {
                node.marked = true;

                for (final Branch branch : node.branches) {
                    if (FillMaxPath(branch.toNode) == INFINITY) return INFINITY;
                    for (int j = 0; j < LETTERS; j++) {
                        maxPaths[fromNode][j] = Math.max(maxPaths[fromNode][j], maxPaths[branch.toNode][j]);
                    }
                }

                maxPaths[fromNode][node.letter - 'a']++;
                node.calculated = true;
                node.marked = false;
                return OK;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        final FastScanner scanner = new FastScanner();
        String str = scanner.nextLine();
        String[] ss = str.split(" ");
        final int n = Integer.parseInt(ss[0]);
        final int m = Integer.parseInt(ss[1]);

        final Graf graf = new Graf(n);

        str = scanner.nextLine();
        for (int i = 0; i < n; i++) {
            graf.nodes[i] = new Node(str.charAt(i));
        }
        for (int i = 0; i < m; i++) {
            final int fromNode = scanner.nextInt() - 1;
            final int toNode = scanner.nextInt() - 1;
            if (fromNode == toNode) {
                System.out.println(INFINITY);
                return;
            }
            graf.nodes[fromNode].branches.add(new Branch(toNode));
        }

        final int maxPath = graf.GetMaxPath();
        System.out.println(maxPath);
    }
}
