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 sys
import math
import heapq
from collections import defaultdict as dd
from collections import OrderedDict as od
from collections import deque
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key
from functools import lru_cache
from bisect import bisect_left as bs_l
from bisect import bisect_right as bs_r
input = sys.stdin.readline
mod=10**9+7
sys.setrecursionlimit(10**5)
#T=int(input())
#for _ in range(T):
n,e=map(int,input().split())
s=input().strip()
gr=dd(list)
indeg=[0]*n
for _ in range(e):
    u,v=map(int,input().split())
    gr[u-1].append(v-1)
    indeg[v-1]+=1
fr=[[0]*26 for _ in range(n)]
qu=deque([])
c=0
for i in range(n):
    if indeg[i]==0:
        qu.append(i)
        fr[i][ord(s[i])-97]+=1
        c+=1

while len(qu):
    x=qu.popleft()
    for ng in gr[x]:
        indeg[ng]-=1
        for i in range(26):
            fr[ng][i]=max(fr[ng][i],fr[x][i])
        if indeg[ng]==0:
            qu.append(ng)
            fr[ng][ord(s[ng])-97]+=1
            c+=1
if c!=n:
    print(-1)
else:
    ans=0
    for i in fr:
        ans=max(ans,max(i))
    print(ans)
