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.codeforces;

import com.sun.security.jgss.GSSUtil;

import java.io.*;
import java.util.*;

public class Solution {
    static String label;
    static ArrayList<Integer> graph[];
//    static boolean vis[];
//    static HashMap<Integer, int[]> dp=new HashMap<>();
//    static int max=0;
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);

               int n=input.nextInt();
               int m=input.nextInt();

              label=input.next();
               graph=new ArrayList[n];
        for (int i = 0; i <n ; i++) {
            graph[i]=new ArrayList<>();
        }
        int in[]=new int[n];
            for (int i = 0; i <m ; i++) {
                int start=input.nextInt();
                int end=input.nextInt();
                in[end-1]++;
                graph[start-1].add(end-1);
            }

            Queue<Integer> queue=new ArrayDeque<>();
            int dp[][]=new int[n][26];
        for (int i = 0; i <n ; i++) {
            if (in[i]==0){
                dp[i][label.charAt(i)-'a']++;
                queue.add(i);
            }
        }
        int couunt=0;
        while (queue.size()>0){
            int child=queue.remove();
            for (int node:graph[child]) {
                for (int i = 0; i <26 ; i++) {
                    if (i==label.charAt(node)-'a'){
                        dp[node][i]=Math.max(dp[node][i],dp[child][i]+1);
                    }else {
                        dp[node][i]=Math.max(dp[node][i],dp[child][i]);
                    }
                }
                if (--in[node]==0){
                    queue.add(node);
                }

            }
            couunt++;
        }
        if (couunt<n){
            System.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]);
                }
            }
            System.out.println(max);
        }


          
        }

//    static boolean flag=false;

//    private static int[] dfs(int i,int fre[]) {
//
//
//        if (vis[i]){
//            if (!dp.containsKey(i)) {
//                flag = true;
//                return new int[26];
//            }else {
//                return dp.get(i);
//            }
//        }
//            vis[i]=true;
//        fre[label.charAt(i)-'a']++;
//        max=Math.max(max,fre[label.charAt(i)-'a']);
//
//
//
//
//         int ans[]=new int[26];
//        for (int child:graph[i]) {
//            int f[]=dfs(child,Arrays.copyOf(fre,fre.length));
////            int f[]=dfs(child,fre);
//            if (flag) return new int[26];
//            for (int j = 0; j <26 ; j++) {
//                ans[j]+=f[j];
//            }
//
//
//
//        }
//        ans[label.charAt(i)-'a']++;
//
//        dp.put(i,ans);
//         return ans;
//    }


}



