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.
//package com.company;
import java.util.*;
import java.io.IOException;

public class Main {

    public static void main(String args[]) throws IOException {
        Scanner in  = new Scanner(System.in);
//        int t = in.nextInt();
        int t=1;
        for (int jay = 0; jay < t; jay++) {
            int n = in.nextInt();
            int k = in.nextInt();
            graph g =  new graph(n);
            g.lol = in.next();

            for(int i=0;i<k;i++){
                g.addE(in.nextInt()-1,in.nextInt()-1);
            }
            int ans = 0;

            for(int i=0;i<n;i++)
            {
                int tmp=0;
                if(g.visit[i]==0) tmp = g.dfs(i);
                if(tmp==-1) {ans=-1;break;}
                else{
                    for(int z:g.arr[i]){
//                        System.out.print(z+" ");
                        ans = Math.max(ans,z);
                    }
                }
            }
            System.out.println(ans);
        }
    }

    static class graph{
        int N;
        int[] visit;
        int[][] arr;
        List<Integer>[] Edges;
        String lol;

        graph(int n){
            N = n;
            Edges = new ArrayList[n];
            visit = new int[n];
            arr = new int[n][26];
            for(int i=0;i<n;i++){
                Edges[i] = new ArrayList<>();
            }
        }
        public void addE(int u,int v){
            Edges[u].add(v);
        }

        public int dfs(int x){
            visit[x] = 1;
            int val = 0;

            for(int i=0;i<Edges[x].size();i++){
                int cur = Edges[x].get(i);
                if(visit[cur]==1) {
                    return -1;
                }
                else if(visit[cur]==0){
                    if(dfs(cur)==-1) return -1;
                    update(x,cur);
                }
                else if(visit[cur]==2){
                    update(x,cur);
                }
            }
            arr[x][lol.charAt(x)-'a'] +=1;

            if(false){
                System.out.print("\t");
                for(int it=0;it<26;it++)System.out.print(arr[x][it]+" ");
                System.out.println("\t");
            }

            visit[x] = 2;
            return val;
        }

        private void update(int par,int child) {
            for(int x=0;x<26;x++){
                arr[par][x] = Math.max(arr[par][x],arr[child][x]);
            }
        }
    }
    private static String rev(String s){
        return new StringBuffer(s).reverse().toString();
    }

    private static boolean isPrime(double n) {
//        no two power
        double x  = Math.sqrt(n);
        int i=3;
        int c=0;

        while(i<=x){
            if(n%i==0) c+=1;
            if(c>=1) return false;
            i+=2;
        }
        if(c==0) return true;
        return false;
    }
    public static void showArr(int[] arr){
        int n=arr.length;
        for(int i=0;i<n;i++){
            System.out.print(arr[i]+" ");
        }
    }
    public static long gcd(long x, long y) {
        if (x == 0)
            return y;
        return gcd(y % x, x);
    }
    public static boolean twoPow (long n)
    {
        return n!=0 && ((n&(n-1)) == 0);
    }
}