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

public class a12{
    static int maxval;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int dp[][]=new int[n][26];
        int x[]=new int[m],y[]=new int[m];
        String s=sc.next();
        for(int i=0;i<m;i++)
        {
            x[i]=sc.nextInt();
            y[i]=sc.nextInt();
        }
        ArrayList<Integer> g[]=new ArrayList[n];
        for(int i=0;i<n;i++)
            g[i]=new ArrayList<Integer>();
        int in[]=new int[n];
        for(int i=0;i<m;i++)
        {
            g[x[i]-1].add(y[i]-1);
            in[y[i]-1]+=1;
        }
        if(cycle(g,in))
            {
                System.out.println(-1);
                return;
            }
        boolean vis[]=new boolean[n];
        maxval=0;
        for(int i=0;i<n;i++)
        {
            if(!vis[i])
                dfsUtil(g,i,dp,vis,s);
        }
        // for(int i=0;i<n;i++)
        // {
        //     for(int j=0;j<26;j++)
        //     System.out.print(dp[i][j]+" ");
        //     System.out.println();
        // }
        System.out.println(maxval);
        


    }
    public static void dfsUtil(ArrayList<Integer> g[],int i,int dp[][],boolean vis[],String s){
        vis[i]=true;
        dp[i][s.charAt(i)-'a']+=1;
        int a[]=new int[26];
        for(int j=0;j<g[i].size();j++)
        {
            int in=g[i].get(j);
            if(!vis[in])
                dfsUtil(g,in,dp,vis,s);
            for(int ik=0;ik<26;ik++)
                a[ik]=Math.max(dp[in][ik],a[ik]);

        }
        for(int ik=0;ik<26;ik++)
        {
            dp[i][ik]+=a[ik];
            maxval=Math.max(dp[i][ik],maxval);
        }
    }
    public static boolean cycle(ArrayList<Integer> g[],int in[]){
        int cnt=0,n=in.length;
        Queue<Integer> q=new LinkedList<>();
        for(int i=0;i<n;i++)
        if(in[i]==0)
            q.add(i);
        while(!q.isEmpty())
        {
            int ind=q.poll();
            cnt+=1;
            for(int i=0;i<g[ind].size();i++)
            {
                int p=g[ind].get(i);
                in[p]-=1;
                if(in[p]==0)
                    q.add(p);
            }
        }
        return !(cnt==n);
    }
}