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.
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
 
n,m=map(int,input().split())
l=list(input())
degree=[0 for i in range(n)]
graph=defaultdict(list)
for i in range(m):
	a,b=map(int,input().split())
	a-=1
	b-=1
	graph[a].append(b)
	degree[b]+=1
q=deque()
for i in range(n):
	if degree[i]==0:
		q.append(i)
count=0
ans=0
# print(degree)
dp=[[0 for i in range(26)] for i in range(n)]
while count<n and q:
	x=q.popleft()
	count+=1
	# print(ord(l[x])-97)
	dp[x][ord(l[x])-97]+=1
	for i in graph[x]:
		for j in range(26):
			dp[i][j]=max(dp[i][j],dp[x][j])
		degree[i]-=1
		if degree[i]==0:
			q.append(i)
if count!=n:
	print(-1)
else:
	ans=0
	for i in range(n):
		ans=max(ans,max(dp[i]))
	print(ans)
 
        
'''for _ in range(int(input())):
    n,q=map(int,input().split())
    s=input()
    d={}
    for i in s:
        if i in d:
            d[i]+=1
        else:
            d[i]=1
    s=list(s)
    for i in range(q):
        m=input()
        if m[0]=='1':
            x,y,z=m.split()
            x=int(x)
            y=int(y)
            d[s[y-1]]-=1
            s[y-1]=z
            if z in d:
                d[z]+=1
            else:
                d[z]=1
        else:
            p,q=m.split()
            q=int(q);a=[]
            value=list(d.values())
            value=list(set(value))
            value.sort(reverse=True)
            if (q-1)>=len(value):
                print(-1)
            else:
                f=value[q-1]
                a=[]
                for k in d:
                    if d[k]==f:
                        a.append(k)
                a.sort()
                print(a[0])'''
        
    
'''for _ in range(int(input())):
    n,m=map(int,input().split())
    arr=[1]*(n+1)
    var=0
    for i in range(2,n):
        a=m%i
        var+=arr[a]
        for j in range(a,n,i):
            arr[j]+=1
    print(var)'''
            
'''for _ in range(int(input())):
    n,m=map(int,input().split())
    s=0
    for i in range(2,n+1):
        y=m%i;count=0;arr=[]
        k=m-y;j=1
        while j*j<k:
            if (m-y)%j==0:
                arr.append(j)
            j+=1
        j=0
        while True:
            if j==len(arr) or arr[j]>=i:
                break
            count+=1
            j+=1
        s+=count
    print(s)'''

'''if o>x:
        print(3)
    elif x-o>1:
        print(3)
    elif x>o  and x_win==1 and o_win==0:
        print(1)
    elif x==o and o_win==1 and x_win==0:
        print(1)
    elif s==0 and (x_win+o_win==0):
        print(1)
    elif s==0 and x_win==2:
        print(1)
    elif s>0 and x_win+o_win==0:
        print(2)
    else:
        print(3)'''
'''for _ in range(int(input())):
    arr=[]
    for i in range(3):
        x=input()
        arr.append(x)
    s=0;x=0;o=0
    for i in range(3):
        st=list(arr[i])
        for j in st:
            if j=='_':
                s+=1
            elif j=='X':
                x+=1
            else:
                o+=1
        print(s,x,o)
    if s==0:
        if x==5 and o==4:
            print(1)
        else:
            print(3)
    else:
        if s%2==1 and x==o:
            print(2)
        elif s%2==0 and x==o+1:
            print(2)
        else:
            print(3)'''
        
'''n=int(input())
arr=[]
for i in range(n):
   arr.append(int(input()))
m=float('-inf')
for i in range(len(arr)):
   for j in range(i+1,len(arr)):
      x=min(arr[i:j+1])
      m=max(m,x*(j-i+1))
print(m)'''
      
'''
n=int(input())
m=int(input())
k=int(input())
a=[]
for i in range(n):
   a.append(int(input()))
b=[]
for i in range(m):
   b.append(int(input()))
m=max(max(a),max(b))
arr=[0]*(m)
a.sort()
for i in a:
   for j in range(i):
      if arr[j]<k:
         arr[j]+=1
         break
if arr.count(1)!=len(a):
   print(0)
else:
   for i in b:
      for j in range(i):
         if arr[j]<k:
            arr[j]+=1
            break
   print(arr.count(1))'''

'''for _ in range(int(input())):
   n,k=map(int,input().split())
   arr=list(map(int,input().split()))
   arr.sort()
   i=0;flag=0;count=0
   print(arr)
   while i<n:
      if arr[i]%2==0:
         if count==k:
            flag=1
            break
      else:
         count=0
         while i<n and arr[i]&1:
            count+=1
            if count==k:
               flag=1
               break
            i+=1
         
      i+=1
   if flag==1:
      print("Yes")
   else:
      print("No")'''
   
'''from heapq import heappop, heappush, heapify
heap = []
heapify(heap)
heappush(heap, -1 * 10)
heappush(heap, -1 * 30)
heappush(heap, -1 * 20)
heappush(heap, -1 * 400)
print("Head value of heap : "+str(-1 * heap[0]))
print("The heap elements : ")
for i in heap:
    print(-1 * i, end = ' ')
print("\n")
  
element = heappop(heap)
print("The heap elements : ")
for i in heap:
    print(-1 * i, end = ' ')'''

'''from itertools import combinations
arr=list(map(int,input().split()))
perm=list(combinations(arr,4))
x=[];count=0
for i in perm:
   if sum(i)==0:
      count+=1
      
print(count)'''
   




'''from queue import Queue
q=Queue(maxsize=10000)
#function for bfs
def breath_first_search_function(start_variable,adjacency_list):
   global list_storing_color,representative_array,p
   list_storing_color[start_variable-1]="gray"
   q.put(start_variable)
   #while q not become empty
   while not(q.empty()):
      u_vertex=q.get()
      representative_array[u_vertex]=p
      x=adjacency_list[u_vertex]
      for v_vertex in x:
         #making node visited
         if list_storing_color[v_vertex-1]=="white":
            list_storing_color[v_vertex-1]=="gray"
            q.put(v_vertex)
      list_storing_color[u_vertex-1]="black"
   
n=int(input())
arr=list(map(int,input().split()))
my_list1=[]
for _ in range(int(input())):
   x=list(map(int,input().split()))
   my_list1.append(x)
dictionary_1={}
list_storing_color=[]
for i in range(n+1):
   list_storing_color.append("white")
for i in range(1,n+1):
   dictionary_1[i]=set()
#creating adjacency list
for i in range(len(my_list1)):
   dictionary_1[my_list1[i][0]].add(my_list1[i][1])
   dictionary_1[my_list1[i][1]].add(my_list1[i][0])
representative_array=[-1]*(n+1)
p=1
for i in dictionary_1:
   if representative_array[i]==-1:
      breath_first_search_function(i,dictionary_1)
      p+=1
representative_array.pop(0)
d1={}
for i in range(len(representative_array)):
   if representative_array[i] not in d1:
      d1[representative_array[i]]=[i]
   else:
      d1[representative_array[i]].append(i)
y=[]
s=-1
no_of_members=0
for i in d1:
   x=d1[i]
   p=0
   for j in x:
      p+=arr[j]
   if p>s:
      s=p
      y=x
      no_of_members=len(y)
   if p==s:
      z=x
      if no_of_members>len(z):
         no_of_members=len(z)
         y=z
         
         
         
for i in range(len(y)):
   y[i]=y[i]+1
print(*y)'''
      
      
   
