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.util.*;


public class codeForcesSubstring {
    public static void main (String[]args) {

        Scanner scan = new Scanner (System.in);

        int nodeNumber = scan.nextInt();
        int edgeNumber = scan.nextInt();

        String string = scan.next();

        char [] nodeCharacters = new char [nodeNumber];

        for (int i = 0; i < nodeNumber; i++) {
            nodeCharacters[i] = string.charAt(i);
        }

        Hashtable <Integer, ArrayList<Integer>> graph = new Hashtable <Integer, ArrayList<Integer>>();
        Hashtable <Integer, ArrayList<Integer>> copyGraph = new Hashtable <Integer, ArrayList<Integer>>();

        boolean [] nodeIsDependent = new boolean [nodeNumber];
        int [] parentsArray = new int [nodeNumber];

        for (int i = 1; i <= nodeNumber; i++) {
            graph.put(i, new ArrayList<Integer>());
            copyGraph.put(i, new ArrayList<Integer>());
        }

        for (int i = 0; i < edgeNumber; i++) {
            int firstConnect = scan.nextInt();
            int secondConnect = scan.nextInt();

            parentsArray[secondConnect - 1]++;
            nodeIsDependent[secondConnect - 1] = true;

            ArrayList <Integer> temp = graph.get(firstConnect);
            temp.add(secondConnect);
            graph.put(firstConnect, temp);

            ArrayList <Integer> tempTwo = copyGraph.get(firstConnect);
            tempTwo.add(secondConnect);
            copyGraph.put(firstConnect, tempTwo);
        }

        ArrayList <Integer> topoSortList = new ArrayList <Integer>();
        Queue <Integer> goodNodes = new LinkedList <Integer>();

        for (int i = 0; i < nodeNumber; i++) {
            if (nodeIsDependent[i] == false) {
                goodNodes.add(i + 1);
            }
        }

        int [][] dp = new int [nodeNumber][26];
        int greatest = 0;

        while (goodNodes.isEmpty() == false) {
            int current = goodNodes.poll();
            topoSortList.add(current);

            ArrayList <Integer> children = graph.get(current);

            char currentNodeCharacter = nodeCharacters[current - 1];
            int ascii = ((int)currentNodeCharacter) - 'a';

            //System.out.println(currentNode + " " + ascii);
            dp[current - 1][ascii] += 1;
            greatest = Math.max(greatest, dp[current - 1][ascii]);

            for (int j = 0; j < children.size(); j++) {
                for (int k = 0; k < 26; k++) {
                    dp[children.get(j) - 1][k] = Math.max(dp[children.get(j) - 1][k], dp[current - 1][k]);
                    greatest = Math.max(greatest, dp[children.get(j) - 1][k]);
                }
            }

            graph.remove(current);

            for (int i = 0; i < children.size(); i++) {
                parentsArray[children.get(i) - 1]--;

                if (parentsArray[children.get(i) - 1] == 0) {
                    goodNodes.add(children.get(i));
                }
            }
        }

        if (graph.size() >= 1) {
            System.out.println(-1);
        }
        else {
            System.out.println(greatest);
        }

        /*
        System.out.println("TOPO SORT: ");

        for (int i = 0; i < nodeNumber; i++) {
            System.out.print(topoSortList.get(i) + " ");
        }
        */
        
        /*
        for (int i = 0; i < nodeNumber; i++) {
            for (int j = 0; j < 26; j++) {
                dp[i][j] = 0;
            }
        }
        

        for (int i = 0; i < nodeNumber; i++) {

            ArrayList <Integer> children = copyGraph.get(currentNode);

            for (int j = 0; j < children.size(); j++) {
                for (int k = 0; k < 26; k++) {
                    //System.out.println(children.get(i) + " " + dp[children.get(j) - 1][k] + " " + currentNode + " " + dp[currentNode - 1][k] + " " + k);
                    
                }
            }
        }
        
        System.out.println("");

        for (int i = 0; i < nodeNumber; i++) {
            for (int j = 0; j < 26; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println("");
        }
        */
    }
}
