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.*;
import java.io.*;
import java.math.BigInteger;

public class MainD
{
    static int mod = (int) (1e9+7);
    static InputReader in;
    static PrintWriter out;
    static int[][] g;
    static char[] arr;
    static boolean[] vis;
    static boolean[] stack;
    
    static boolean ok(int u){
        if(!vis[u]){
            
            vis[u] = true;
            stack[u] = true;
            for(int v : g[u]){
                if(!vis[v] && ok(v))
                    return true;
                else if(stack[v])
                    return true;
            }
            
        }
        stack[u] = false;
        return false;
    }
    
    static int[] dp;
    
    static int get(int u, char c){
        if(dp[u] != -1)
            return dp[u];
        int mx = 0;
        
        for(int v : g[u]){
            mx = Math.max(mx,get(v, c));
        }
        
        return dp[u] = mx + (arr[u] == c ? 1 : 0);
    }
    
    public static void main(String[] args)
    {

        in = new InputReader(System.in);
        out = new PrintWriter(System.out);       
        
        int n = in.nextInt();
        int m = in.nextInt();
        g = new int[n][];
        arr = in.readString().toCharArray();
        int[] u = new int[m];
        int[] v = new int[m];
        int[] arr = new int[n];
        
        for(int i = 0; i < m; i++){
            u[i] = in.nextInt() - 1;
            v[i] = in.nextInt() - 1;
            arr[u[i]]++;
        }
        
        for(int i = 0; i < n; i++){
            g[i] = new int[arr[i]];
            arr[i] = 0;
        }

        for(int i = 0; i < m; i++){
            g[u[i]][arr[u[i]]++] = v[i];
        }
        vis = new boolean[n];
        stack = new boolean[n];
        boolean flag = false;
        
        for(int i = 0; i < n; i++){
            if(ok(i)){
                flag = true;
                break;
            }
        }
        
        if(flag){
            out.println(-1);
            out.close();;
            return;
        }
        
        int ans = 0;
        dp = new int[n];
        
        for(char c = 'a'; c <= 'z'; c++){
            Arrays.fill(dp, -1);
            for(int i = 0; i < n; i++){
                int x = get(i, c);
                ans = Math.max(ans, x);
            }
        }
        
        out.println(ans);
        out.close();  
    }
     
    static class Pair implements Comparable<Pair>
    {

        int x,y,k,i;

        Pair (int x,int y, int k)
        {
                this.x = x;
                this.y = y;
                this.k = k;
        }

        Pair (int x,int y, int k, int i)
        {
                this.x = x;
                this.y = y;
                this.k = k;
                this.i = i;
        }
        
        public int compareTo(Pair o)
        {
            return Integer.compare(this.k,o.k);
                //return 0;
        }

        public boolean equals(Object o)
        {
            if (o instanceof Pair)
            {
                Pair p = (Pair)o;
                return p.x == x && p.y==y;
            }
            return false;
        }

        @Override
        public String toString()
        {
            return x + " "+ y + " "+k;
        }

        /*public int hashCode()
        {
            return new Long(x).hashCode() * 31 + new Long(y).hashCode();
        }*/

    } 

    static long add(long a,long b){
        long x=(a+b);
        while(x>=mod) x-=mod;
        return x;
    }

    static long sub(long a,long b){
        long x=(a-b);
        while(x<0) x+=mod;
        return x;
    }
    
    static long mul(long a,long b){
        long x=(a*b);
        while(x>=mod) x-=mod;
        return x;
    }
    
    static String rev(String s){
        StringBuilder sb=new StringBuilder(s);
        sb.reverse();
        return sb.toString();
    }
    
    static long gcd(long x,long y)
    {
        if(y==0)
                return x;
        else
                return gcd(y,x%y);
    }

    static int gcd(int x,int y)
    {
        if(y==0)
                return x;
        else 
                return gcd(y,x%y);
    }

    static long pow(long n,long p,long m)
    {
         long  result = 1;
          if(p==0){
            return 1;
          }
          
        while(p!=0)
        {
            if(p%2==1)
                result *= n;
            if(result >= m)
               result %= m;
            p >>=1;
            n*=n;
            if(n >= m)
                n%=m;
        }
        
        return result;
    }

    static long pow(long n,long p)
    {
        long  result = 1;
          if(p==0)
            return 1;

        while(p!=0)
        {
            if(p%2==1)
                result *= n;	    
            p >>=1;
            n*=n;	    
        }
        return result;
    }

    static void debug(Object... o)
    {
            System.out.println(Arrays.deepToString(o));
    }

    static class InputReader
    {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream)
        {
                this.stream = stream;
        }

        public int snext()
        {
                if (snumChars == -1)
                        throw new InputMismatchException();
                if (curChar >= snumChars)
                {
                        curChar = 0;
                        try
                        {
                                snumChars = stream.read(buf);
                        } catch (IOException e)
                        {
                                throw new InputMismatchException();
                        }
                        if (snumChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }

        public int nextInt()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                int res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public long nextLong()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                long res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public int[] nextIntArray(int n)
        {
                int a[] = new int[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextInt();
                }
                return a;
        }

        public long[] nextLongArray(int n)
        {
                long a[] = new long[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextLong();
                }
                return a;
        }

        public String readString()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isSpaceChar(c));
                return res.toString();
        }

        public String nextLine()
        {
                int c = snext();
                while (isSpaceChar(c))
                        c = snext();
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isEndOfLine(c));
                return res.toString();
        }

        public boolean isSpaceChar(int c)
        {
                if (filter != null)
                        return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c)
        {
                return c == '\n' || c == '\r' || c == -1;
        }

        public interface SpaceCharFilter
        {
                public boolean isSpaceChar(int ch);
        }

    }
}    
