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 javafx.util.*;

public class Solution
{
       static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                                 BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
    static int parent(int x , int p[])
    {
           if(p[x] == x)
           return x;
           
           return (p[x] = parent(p[x],p));
    }
    
    static void union(int a , int b , int p[] , int size[])
    {
           a = parent(a,p);
           b = parent(b,p);
           
           if(size[a] < size[b])
           {
                  int temp = a;
                  a = b;
                  b = temp;
           }
           p[b] = a;
           size[a] += size[b];
    }
    
    static void dfs(int n , LinkedList<Integer> arr[] , boolean vis[] , Stack<Integer> topo)
    {
           vis[n] = true;
           for(Integer i : arr[n])
           {
                  if(!vis[i])
                  dfs(i,arr,vis,topo);
           }
           topo.push(n);
    }
    static void dfs2(int n , LinkedList<Integer> arr[] , boolean vis[] , int is[])
    {
           vis[n] = true;
           for(Integer i : arr[n])
           {
                  if(!vis[i] && is[i] == 1)
                  {
                        
                         dfs2(i,arr,vis,is);
                  }
           }
           
           
    }
    
    static int max(int pos , int curr , int a[] , int b[] , int k ,int dp[][] , boolean vis[][])
    {
           if(pos == a.length)
           {
                  if(curr == 200000)
                  return 0;
                  
                  return Integer.MIN_VALUE;
           }
           
          if(vis[pos][curr])
          return dp[pos][curr];
          
          vis[pos][curr] = true;
          dp[pos][curr] = Math.max(a[pos]+max(pos+1,curr+a[pos]-k*b[pos],a,b,k,dp,vis),
                                  max(pos+1,curr,a,b,k,dp,vis));
                                  
       return dp[pos][curr];
          
    }
   public static void main(String []args) throws IOException
   {
          Scanner sc = new Scanner(System.in);
          int n = sc.nextInt();
          int m = sc.nextInt();
          boolean vis[] = new boolean[n+1];
          int vv = 0;
          int in[] = new int[n+1];
          LinkedList<Integer> arr[] = new LinkedList[n+1];
          for(int i = 1 ; i <= n  ;i++)
          {
                 arr[i] = new LinkedList<Integer>();
          }
          sc.nextLine();
          String s  = sc.nextLine();
         HashMap<Pair<Integer,Integer>,Integer> map = new HashMap<Pair<Integer,Integer>,Integer>();
         
          for(int i = 0 ; i < m ; i++)
          {
                 int x = sc.nextInt();
                 int y = sc.nextInt();
                 Pair<Integer,Integer> pp = new Pair<Integer,Integer>(x,y);
                 if(!map.containsKey(pp))
                 {
                 arr[x].add(y);
                 in[y]++;
                 map.put(pp,1);
                 }
          }
          Queue<Integer> q = new LinkedList<Integer>();
          int dp[][] = new int[n+1][26];
          for(int i = 1 ; i <= n ; i++)
          {
                 if(in[i] == 0)
                 {
                 q.add(i);
                 dp[i][s.charAt(i-1)-'a'] = 1;
                 //System.out.println(i);
                 }
          }
          
          
         
          while(q.size() > 0)
          {
                
                 int v = q.remove();
                 // System.out.println(v);
                 vv++;
                 for(Integer i : arr[v])
                 {
                        for(int j = 0 ; j < 26 ; j++)
                        {
                               if(j == s.charAt(i-1)-'a')
                               dp[i][j] = Math.max(dp[i][j],dp[v][j]+1);
                               
                               else
                               dp[i][j] = Math.max(dp[i][j],dp[v][j]);
                        }
                        
                        in[i]--;
                        if(in[i] == 0)
                        {
                               q.add(i);
                        }
                 }
          }
          if(vv != n)
          System.out.println("-1");
          
          else
          {
                 int max = 0;
                 for(int i = 1 ; i <= n ; i++)
                 {
                        for(int j = 0 ; j < 26 ; j++)
                        {
                                max = Math.max(max,dp[i][j]);
                        }
                 }
                 System.out.println(max);
          }
   }
}