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.util.ArrayList;
import java.util.List;

/**
 * Resolve of Task185 on Codeforces.
 * https://codeforces.com/contest/919/problem/D?locale=ru
 *
 * @author Kirill
 * @since 24.04.2021
 */
public class Task919D {
    List<List<Integer>> graph;
    boolean[] dontCheck;
    boolean[] used;
    byte[] colours;
    int[][] values;
    String letters;

    public static void main(String[] args) {
        Task919D task = new Task919D();
        task.resolve();
    }

    private void resolve() {
        inputData();
        int maxLength = Integer.MIN_VALUE;

        if (checkForCycles()) {
            System.out.println(-1);
            return;
        }

        for (int i = 0; i < graph.size(); i++) {
            if (!dontCheck[i] && !used[i]) {
                getMaxStringLength(i);
            }

            maxLength = Math.max(maxLength, getMaxValue(values[i]));
        }

        System.out.println(maxLength);
    }

    private int getMaxValue(int[] letterCount) {
        int maxLetterCount = Integer.MIN_VALUE;
        for (int count : letterCount) {
            maxLetterCount = Math.max(maxLetterCount, count);
        }

        return maxLetterCount;
    }

    private void inputData() {
        try (BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in))) {
            String[] strings = bufferedReader.readLine().split(" ");
            int peakCount = Integer.parseInt(strings[0]);
            int edgeCount = Integer.parseInt(strings[1]);
            createGraph(peakCount);
            dontCheck = new boolean[peakCount];
            used = new boolean[peakCount];
            values = new int[peakCount][26];

            letters = bufferedReader.readLine();
            for (int i = 0; i < edgeCount; i++) {
                strings = bufferedReader.readLine().split(" ");
                int peakFrom = Integer.parseInt(strings[0]) - 1;
                int peakTo = Integer.parseInt(strings[1]) - 1;

                graph.get(peakFrom).add(peakTo);
                dontCheck[peakTo] = true;
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void getMaxStringLength(int peakFrom) {
        used[peakFrom] = true;
        for (int peakTo : graph.get(peakFrom)) {
            if (!used[peakTo]) {
                getMaxStringLength(peakTo);
            }

            mergeParentAndChild(values[peakFrom], values[peakTo]);
        }

        values[peakFrom][letters.charAt(peakFrom) - 'a']++;
    }

    private void mergeParentAndChild(int[] parent, int[] child) {
        for (int i = 0; i < parent.length; i++) {
            parent[i] = Math.max(child[i], parent[i]);
        }
    }

    private boolean checkForCycles() {
        colours = new byte[graph.size()];
        for (int i = 0; i < graph.size(); i++) {
            if (colours[i] == 0 && findCycle(i)) {
                return true;
            }
        }

        return false;
    }

    private boolean findCycle(int peakFrom) {
        colours[peakFrom] = 1;
        for (int peakTo : graph.get(peakFrom)) {
            if (colours[peakTo] == 1) {
                return true;
            } else if (colours[peakTo] == 0) {
                if (findCycle(peakTo)) {
                    return true;
                }
            }
        }

        colours[peakFrom] = -1;
        return false;
    }

    private void createGraph(int peakCount) {
        graph = new ArrayList<>(peakCount);
        for (int i = 0; i < peakCount; i++) {
            graph.add(new ArrayList<>());
        }
    }
}
