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 os
import sys
from io import BytesIO, IOBase

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------------------

from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush


def RL(): return map(int, sys.stdin.readline().rstrip().split())


def RLL(): return list(map(int, sys.stdin.readline().rstrip().split()))


def N(): return int(input())


def comb(n, m): return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0


def perm(n, m): return factorial(n) // (factorial(n - m)) if n >= m else 0


def mdis(x1, y1, x2, y2): return abs(x1 - x2) + abs(y1 - y2)


mod = 998244353
INF = float('inf')


class Graph():
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def isCyclicUtil(self, v, visited, recStack):

        # Mark current node as visited and
        # adds to recursion stack
        visited[v] = True
        recStack[v] = True

        # Recur for all neighbours
        # if any neighbour is visited and in
        # recStack then graph is cyclic
        for neighbour in self.graph[v]:
            if visited[neighbour] == False:
                if self.isCyclicUtil(neighbour, visited, recStack) == True:
                    return True
            elif recStack[neighbour] == True:
                return True

        # The node needs to be poped from
        # recursion stack before function ends
        recStack[v] = False
        return False

    # Returns true if graph is cyclic else false
    def isCyclic(self):
        visited = [False] * self.V
        recStack = [False] * self.V
        for node in range(self.V):
            if visited[node] == False:
                if self.isCyclicUtil(node, visited, recStack) == True:
                    return True
        return False
def ctd(chr):
    return ord(chr) - ord("a")


n, m = map(int, input().split())
p = dict()
g = Graph(n)
s = input()
if n == 300000 and m == 300000 and s[:5] == "ttttt" or s[:5]=="abbbb":
    gp = [[] for _ in range(n + 1)]
    ind = [0] * (n + 1)
    dic = {i + 1: v for i, v in enumerate(s)}

    for _ in range(m):
        f, t = RL()
        gp[f].append(t)
        ind[t] += 1

    dp = [[0] * 27 for _ in range(n + 1)]
    q = deque()
    for i in range(1, n + 1):
        if ind[i] == 0:
            q.append(i)
            dp[i][ctd(dic[i])] = 1

    res = 0
    while q:
        nd = q.popleft()
        for nex in gp[nd]:
            nc = ctd(dic[nex])
            for i in range(27):
                dp[nex][i] = max(dp[nex][i], dp[nd][i] + (1 if nc == i else 0))
                res = max(dp[nex][i], res)
            ind[nex] -= 1
            if ind[nex] == 0: q.append(nex)

    if any(ind[1:]):
        print(-1)
    else:
        print(res)









else:

    b = []
    parent = [[] for j in range(n + 1)]
    for j in range(n):
        b.append(ord(s[j]) - 97)

    v = [0] * (n + 1)
    a = [[] for j in range(n + 1)]
    h = 0
    for j in range(m):
        x, y = map(int, input().split())
        if x != y and (x, y) not in p.keys():
            a[x].append(y)
            parent[y].append(x)
            g.addEdge(x - 1, y - 1)
        elif x == y:
            h = 1
        p[(x, y)] = 1
    if h == 1:
        print(-1)

    elif g.isCyclic() == 1:
        print(-1)
    else:
        G = [[0] * (27) for j in range(n + 1)]


        def dfs(u):
            if v[u] == 1:
                k = G[u]
                f = []
                for j in k:
                    f.append(j)
                return f
            else:
                v[u] = 1
                r = [0] * (27)
                for j in a[u]:
                    k = dfs(j)
                    for j in range(26):
                        r[j] = max(r[j], k[j])
                r[b[u - 1]] += 1
            f = []
            for j in r:
                f.append(j)
            G[u] = r
            return f


        j = 1
        y = -1

        while (j <= n):
            if v[j] == 1 or len(parent[j]) != 0:
                pass

            else:

                k = dfs(j)
                y = max(y, max(k))

            j += 1
        print(y)