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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Collection;
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main
{
    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD
    {
        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            int N = in.nextInt(), M = in.nextInt();
            in.nextLine();
            String word = in.nextLine();

            Graph graph = new Graph(N);
            int[] indeg = new int[N];
            int[][] dp = new int[N][26];
            Queue<Integer> queue = new LinkedList<Integer>();

            while (M-- > 0) {
                int i = in.nextInt() - 1;
                int j = in.nextInt() - 1;
                graph.addEdge(i, j);

                indeg[j]++;
            }

            for (int i = 0; i < N; i++)
                if (indeg[i] == 0) {
                    queue.add(i);
                    dp[i][word.charAt(i) - 'a'] = 1;
                }

            int remainingEdges = N;
            while (!queue.isEmpty()) {
                int curr = queue.poll();
                remainingEdges--;

                for (int succEdge : graph.adj[curr]) {
                    for (int alpha = 0; alpha < 26; alpha++)
                        dp[succEdge][alpha] = Math.max(dp[succEdge][alpha], dp[curr][alpha] + ((word.charAt(succEdge) - 'a') == alpha ? 1 : 0));

                    if (--indeg[succEdge] == 0)
                        queue.add(succEdge);
                }
            }

            if (remainingEdges != 0) {
                out.println(-1);
            } else {
                int max = 0;
                for (int i = 0; i < N; i++)
                    for (int j = 0; j < 26; j++)
                        max = Math.max(max, dp[i][j]);

                out.println(max);
            }
        }

        class Graph
        {
            int N;
            ArrayList<Integer>[] adj;

            Graph(int NN)
            {
                N = NN;
                adj = new ArrayList[N];
                for (int i = 0; i < N; i++)
                    adj[i] = new ArrayList<>();
            }

            void addEdge(int i, int j)
            {
                adj[i].add(j);
            }

        }

    }
}

