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.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;




/**
 *
 * @author Yan
 */
public class Test {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt(),m=in.nextInt();
        String s=in.next();
        ArrayList<Integer>[] mas=new ArrayList[n+1];
        for (int i=1; i<=n; i++) mas[i]=new ArrayList<Integer>();
        int[] ar=new int[n+1];
        int[][] pot=new int[n+1][26];
        for (int i=0; i<m; i++){
            int a=in.nextInt(),b=in.nextInt();
            ar[b]++;
            mas[a].add(b);
        }
        Queue<Integer> och=new ArrayDeque<>();
        for (int i=1; i<=n; i++){
            if (ar[i]==0){
                och.offer(i);
                pot[i][s.charAt(i-1)-'a']++;
            }
        }
        int p=0;
        while (p<n&&och.size()!=0){
            int el=och.poll();
            for (int i:mas[el]){
                for (int j=0; j<26; j++){
                    if (j==s.charAt(i-1)-'a'){
                        pot[i][j]=Math.max(pot[el][j]+1,pot[i][j]);
                    }
                    else{
                        pot[i][j]=Math.max(pot[el][j],pot[i][j]);
                    }
                }
                if (--ar[i]==0) och.offer(i);
            }
            p++;
        }
        if (p<n){
            System.out.print(-1);
            return;
        }
        int ans=0;
        for (int arr[]:pot){
            for (int i:arr){
                ans=Math.max(ans, i);
            }
        }
        System.out.print(ans);
    }
}