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, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
#INF = float('inf')
mod = 998244353

def toposort(graph):
    res, found = [], [0] * len(graph)
    dp = [dd(int) for i in range(n)]
    stack = list(range(len(graph)))
    while stack:
        node = stack.pop()
        if node < 0:
            res.append(~node)
        elif not found[node]:
            found[node] = 1
            stack.append(~node)
            stack += graph[node]

    # cycle check
    ans = 0
    for node in res:
        if any(found[nei] for nei in graph[node]):
            return None
        for child in graph[node]:
            for k in dp[child]:
                dp[node][k] = max(dp[node][k], dp[child][k])
        dp[node][s[node]]+=1
        found[node] = 0
        ans = max(ans, max(dp[node].values()))

    return ans


n,m = mdata()
s = data()
graph = [[] for i in range(n)]
for i in range(m):
    u,v = mdata()
    graph[u-1].append(v-1)
ans = toposort(graph)
if ans == None:
    print(-1)
else:
    print(ans)






