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

public class Beauty2 {
    static final int MOD = 1000000007;

    public static void main(String[] args) throws IOException {
        //sc = new Reader(dir+"/src/test.txt");
//        sc = new Reader();
        Scanner sc = new Scanner(System.in);
        int n, m;
        int[] x, y;
        String abc;

        n = sc.nextInt();
        m = sc.nextInt();
//        sc.readLine();
        sc.nextLine();
        abc = sc.nextLine();
        x = new int[m];
        y = new int[m];
        for (int i = 0; i < m; i++){
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }


        System.out.println(beauty(n,m,abc,x,y));
    }

    public static int beauty(int n,int m,String a,int X[],int Y[])
    {
        char s[]=a.toCharArray();
        int x[]=new int[m+1];
        int y[]=new int[m+1];

        for(int i=0; i<m; i++){
            x[i]=X[i]-1;
            y[i]=Y[i]-1;
        }
        ArrayList<TreeSet<Integer>> adL = new ArrayList<>();
        int[] edgeIn = new int[n];
        for(int i=0; i<n; i++)
            adL.add(new TreeSet<Integer>());

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

            if(!adL.get(x[i]).contains(y[i])){
                adL.get(x[i]).add(y[i]);
                edgeIn[y[i]]++;
            }
        }
        int[][] dp = new int[n][26];
        for(int i=0; i<n; i++)
            dp[i][s[i]-'a'] = 1;

        int max = Integer.MIN_VALUE;
        boolean[] isVisited = new boolean[n];

        ArrayDeque<Integer> q = new ArrayDeque<Integer>();

        for(int i=0; i<n; i++)
            if(edgeIn[i] == 0) q.add(i);

        while(!q.isEmpty()){
            int cur = q.poll();

            isVisited[cur] = true;

            for (int next : adL.get(cur)) {
                edgeIn[next]--;

                for (int j = 0; j < 26; j++) {
                    dp[next][j] = Math.max(dp[next][j], dp[cur][j] + ((j == (s[next] - 'a')) ? 1 : 0));
                    max = Math.max(max, dp[next][j]);
                }

                if (edgeIn[next] == 0)
                    q.add(next);
            }
        }

        for(int i=0; i<n; i++){
            if (!isVisited[i]) {
                return -1;
            }
        }
        return max;

    }

}

/*================================================
    Creation time :        14/05/21, 11:28 AM
    Project name  :        Codechef
    Author        :        anshumandubey
=================================================*/
