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 \leq n, m \leq 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 \leq x, y \leq 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 \to 3 \to 4 \to 5$. The value is $3$ because the letter 'a' appears $3$ times.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Graph algorithms

Graph traversal


Solutions:
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
l = list(input())
deg = [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)
	deg[b] += 1
q = deque()
for i in range(n):
	if deg[i] == 0:
		q.append(i)
count = 0
ans = 0
dp = [[0 for i in range(26)] for i in range(n)]
while count < n and q:
	und = q.popleft()
	count += 1
	dp[und][ord(l[und]) - 97] += 1
	for i in graph[und]:
		for j in range(26):
			dp[i][j] = max(dp[i][j], dp[und][j])
		deg[i] -= 1
		if deg[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)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	c = dict(Counter(l))
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = sys.stdin.readline

def solve():
	(n, m) = li()
	s = si().strip()
	adj = [[] for i in range(n)]
	ind = [0] * n
	for i in range(m):
		(x, y) = li()
		x -= 1
		y -= 1
		adj[x].append(y)
		ind[y] += 1
	ancesstor = set()
	vis = [False] * n
	dp = [[0 for i in range(26)] for j in range(n)]

	@bootstrap
	def dfs(node):
		ancesstor.add(node)
		for kid in adj[node]:
			if kid in ancesstor:
				print(-1)
				exit(0)
				yield (-1)
			if vis[kid] == False:
				vis[kid] = True
				yield dfs(kid)
			for j in range(26):
				dp[node][j] = max(dp[kid][j], dp[node][j])
		dp[node][ord(s[node]) - 97] += 1
		ancesstor.remove(node)
		yield
	for i in range(n):
		if vis[i] == False:
			vis[i] = True
			a = dfs(i)
			if a == -1:
				exit(0)
	ans = 0
	for i in dp:
		ans = max(ans, max(i))
	print(ans)
t = 1
for _ in range(t):
	solve()


input = lambda : stdin.readline().strip()
from sys import stdin, stdout

def INI():
	return int(stdin.readline())

def INL():
	return [int(_) for _ in stdin.readline().split()]

def INS():
	return stdin.readline()

def MOD():
	return pow(10, 9) + 7

def OPS(ans):
	stdout.write(str(ans) + '\n')

def OPL(ans):
	[stdout.write(str(_) + ' ') for _ in ans]
	stdout.write('\n')
from collections import deque
(n, m) = INL()
s = input()
(x, y) = ([], [])
for _ in range(m):
	(a, b) = map(int, input().split())
	x.append(a)
	y.append(b)
l = list(s)
D = [0 for _ in range(n)]
G = {_: [] for _ in range(n)}
for _ in range(m):
	(a, b) = (x[_], y[_])
	a -= 1
	b -= 1
	G[a].append(b)
	D[b] += 1
q = deque()
for _ in range(n):
	if D[_] == 0:
		q.append(_)
c = 0
ans = 0
DP = [[0 for _ in range(26)] for _ in range(n)]
while c < n and q:
	x = q.popleft()
	c += 1
	DP[x][ord(l[x]) - 97] += 1
	for _ in G[x]:
		for __ in range(26):
			DP[_][__] = max(DP[_][__], DP[x][__])
		D[_] -= 1
		if D[_] == 0:
			q.append(_)
if c != n:
	OPS(-1)
else:
	for _ in range(n):
		ans = max(ans, max(DP[_]))
	OPS(ans)


from collections import defaultdict, deque, Counter
import sys
import bisect
import math
input = sys.stdin.readline
mod = 1000000007

def beauty(n, m, s, x, y):
	b = 0
	l = s
	l1 = x
	l2 = y
	f1 = []
	h1 = defaultdict(list)
	for i in range(n):
		f1.append(0)
	for i in range(m):
		(a, b) = (l1[i], l2[i])
		a -= 1
		b -= 1
		h1[a].append(b)
		f1[b] += 1
	q = deque()
	for i in range(n):
		if f1[i] == 0:
			q.append(i)
	count = 0
	ans = 0
	arr1 = [[0 for i in range(26)] for i in range(n)]
	while count < n and q:
		x = q.popleft()
		count += 1
		arr1[x][ord(l[x]) - 97] += 1
		for i in h1[x]:
			for j in range(26):
				arr1[i][j] = max(arr1[i][j], arr1[x][j])
			f1[i] -= 1
			if f1[i] == 0:
				q.append(i)
	for i in range(1):
		if b == 0:
			b = l1[0]
		else:
			b = l1[-1]
	if count != n:
		print(-1)
	else:
		ans = 0
		for i in range(n):
			ans = max(ans, max(arr1[i]))
		print(ans)
(n, m) = map(int, input().split())
s = input()
l1 = []
l2 = []
for i in range(m):
	(a, b) = map(int, input().split())
	l1.append(a)
	l2.append(b)
beauty(n, m, s, l1, l2)


(n, m) = map(int, input().split())
s = ' ' + input()
(ed, dp) = ([], [])
maxi = 300005
for _ in range(n + 1):
	ed.append([])
	dp.append([0] * 26)
(q, deg) = ([0] * maxi, [0] * (n + 1))
for i in range(m):
	(x, y) = map(int, input().split())
	ed[x].append(y)
	deg[y] += 1
(fr, re) = (0, 0)

def funct():
	re = fr = 0
	for i in range(1, n + 1):
		if deg[i] == 0:
			q[re] = i
			re += 1
			dp[i][ord(s[i]) - 97] = 1
	count = 0
	while fr != re:
		u = q[fr]
		fr += 1
		count += 1
		for i in range(len(ed[u])):
			v = ed[u][i]
			for j in range(26):
				x = dp[u][j]
				if j == ord(s[v]) - ord('a'):
					x += 1
				dp[v][j] = max(x, dp[v][j])
			deg[v] -= 1
			if deg[v] == 0:
				q[re] = v
				re += 1
	ans = -9999999
	for i in range(1, n + 1):
		for j in range(26):
			ans = max(ans, dp[i][j])
	return (count == n, ans)
ans1 = funct()
if ans1[0]:
	print(ans1[1])
else:
	print(-1)


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)
(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)


from collections import defaultdict, deque
from sys import stdin
import functools
input = lambda : stdin.readline().strip()

def beautifulPath(n, m, s, x, y):
	degree = [0] * n
	graph = defaultdict(list)
	for i in range(m):
		(a, b) = (x[i], y[i])
		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
	dp = [[0] * 26 for i in range(n)]
	while count < n and q:
		a = q.popleft()
		count += 1
		dp[a][ord(s[a]) - 97] += 1
		for i in graph[a]:
			for j in range(26):
				dp[i][j] = max(dp[a][j], dp[i][j])
			degree[i] -= 1
			if degree[i] == 0:
				q.append(i)
	if count != n:
		return -1
	else:
		return functools.reduce(lambda x, y: x if x > y else y, set((max(dp[i]) for i in range(n))))
(n, m) = map(int, input().split())
s = input()
xList = []
yList = []
for i in range(m):
	(x, y) = map(int, input().split())
	xList.append(x)
	yList.append(y)
finalPath = beautifulPath(n, m, s, xList, yList)
print(finalPath)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_left
(n, m) = map(int, input().split())
l = list(input())
degree = [0 for i in range(n)]
graph = {i: [] for i in range(n)}
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
dp = [[0 for i in range(26)] for i in range(n)]
while count < n and q:
	x = q.popleft()
	count += 1
	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)


from sys import stdin
input = lambda : stdin.readline().strip()
from collections import deque
(n, m) = map(int, input().split())
s = input()
x = []
y = []
for i in range(m):
	(a, b) = map(int, input().split())
	x.append(a)
	y.append(b)

def beauty(n, m, s, x, y):
	l = list(s)
	degree = [0 for i in range(n)]
	graph = {i: [] for i in range(n)}
	for i in range(m):
		(a, b) = (x[i], y[i])
		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
	dp = [[0 for i in range(26)] for i in range(n)]
	while count < n and q:
		x = q.popleft()
		count += 1
		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)
beauty(n, m, s, x, y)


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

def ctd(chr):
	return ord(chr) - ord('a')

def main():
	(n, m) = RL()
	s = input()
	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)
main()


maxi = 300005
(n, m) = map(int, input().split())
s = input()
s = ' ' + s
ed = []
dp = []
for i in range(n + 1):
	ed.append([])
	dp.append([0] * 26)
q = [0] * maxi
front = 0
rear = 0
deg = [0] * (n + 1)
for i in range(m):
	(x, y) = map(int, input().split())
	ed[x].append(y)
	deg[y] += 1

def topSort():
	rear = front = 0
	cnt = 0
	for i in range(1, n + 1):
		if deg[i] == 0:
			q[rear] = i
			rear += 1
			dp[i][ord(s[i]) - 97] = 1
	while front != rear:
		u = q[front]
		front += 1
		cnt += 1
		for i in range(len(ed[u])):
			v = ed[u][i]
			for j in range(26):
				x = dp[u][j]
				if j == ord(s[v]) - ord('a'):
					x += 1
				dp[v][j] = max(x, dp[v][j])
			deg[v] -= 1
			if deg[v] == 0:
				q[rear] = v
				rear += 1
	ans = -1
	for i in range(1, n + 1):
		for j in range(26):
			ans = max(ans, dp[i][j])
	return (cnt == n, ans)
ans = topSort()
if ans[0]:
	print(ans[1])
else:
	print(-1)


from collections import defaultdict, deque, Counter
import sys
import bisect
import math
input = sys.stdin.readline

def beauty(n, m, z, x, y):
	l = z
	degree = [0 for i in range(n)]
	graph = defaultdict(list)
	for i in range(m):
		(a, b) = (x[i], y[i])
		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
	dp = [[0 for i in range(26)] for i in range(n)]
	while count < n and q:
		x = q.popleft()
		count += 1
		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:
		return -1
	else:
		ans = 0
		for i in range(n):
			ans = max(ans, max(dp[i]))
		return ans
(n, m) = map(int, input().split())
s = input()
x = []
y = []
for i in range(m):
	(u, v) = map(int, input().split())
	x.append(u)
	y.append(v)
print(beauty(n, m, s, x, y))


import sys, os, io
from sys import stdin, stdout
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def beautifulpath(n, adj, s):
	queue = deque()
	indeg = [0] * n
	for i in range(n):
		for j in adj[i]:
			indeg[j] += 1
	for i in range(n):
		if indeg[i] == 0:
			queue.append(i)
	topo = []
	count = 0
	dp = [[0 for i in range(26)] for i in range(n)]
	while queue:
		start = queue.popleft()
		topo.append(start)
		count += 1
		dp[start][ord(s[start]) - 97] += 1
		for i in adj[start]:
			for j in range(26):
				dp[i][j] = max(dp[i][j], dp[start][j])
			indeg[i] -= 1
			if indeg[i] == 0:
				queue.append(i)
	if count == n:
		ans = 0
		for i in range(n):
			ans = max(ans, max(dp[i]))
		return ans
	return -1
input = lambda : sys.stdin.readline().strip()
(n, m) = map(int, input().split())
s = input()
adj = []
for i in range(n + 1):
	adj.append([])
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	adj[x].append(y)
ans = beautifulpath(n, adj, s)
print(ans)


from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		to = f(*args, **kwargs)
		if stack:
			return to
		else:
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						return to
					to = stack[-1].send(to)
	return wrappedfunc
import sys
input = sys.stdin.readline
from collections import defaultdict as dd
(n, m) = map(int, input().split())
s = input()
d = dd(list)
lol = 0
for i in range(m):
	(u, v) = map(int, input().split())
	if u == v:
		lol = 1
		print(-1)
		exit()
	d[u].append(v)
vis = [0] * (n + 1)
rvis = [0] * (n + 1)
cou = [0]
dp = [dd(int) for i in range(n + 1)]
mx = [0]
h = [0]

@bootstrap
def dfs(u):
	if h[0] == 1:
		yield
	vis[u] = 1
	rvis[u] = 1
	for i in d[u]:
		if h[0] == 1:
			yield
		if vis[i] == 0:
			yield dfs(i)
			if h[0] == 1:
				yield
		elif rvis[i] == True:
			h[0] = 1
			yield
	rvis[u] = 0
	if h[0] == 1:
		yield
	for i in d[u]:
		for j in dp[i]:
			dp[u][j] = max(dp[u][j], dp[i][j])
			mx[0] = max(mx[0], dp[u][j])
	dp[u][s[u - 1]] += 1
	mx[0] = max(mx[0], dp[u][s[u - 1]])
	yield
for i in range(1, n + 1):
	if vis[i] == 0:
		cou = [0]
		dfs(i)
if h[0]:
	print(-1)
else:
	print(mx[0])


from os import path
import sys, time
mod = int(1000000000.0 + 7)
from math import ceil, floor, gcd, log, log2, factorial, sqrt
from collections import defaultdict, Counter, OrderedDict, deque
from itertools import combinations, accumulate
from bisect import *
from functools import reduce
from operator import mul
star = lambda x: print(' '.join(map(str, x)))
grid = lambda r: [lint() for i in range(r)]
stpr = lambda x: sys.stdout.write(f'{x}' + '\n')
INF = float('inf')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
import sys
from sys import stdin, stdout
from collections import *
from math import gcd, floor, ceil
from copy import deepcopy

def st():
	return list(stdin.readline().strip())

def inp():
	return int(stdin.readline())

def inlt():
	return list(map(int, stdin.readline().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, stdin.readline().split())

def pr(n):
	return stdout.write(str(n) + '\n')

def check(a):
	for i in a:
		if i:
			return True
	return False

def change(x):
	return ord(x) - ord('a')

def solve():
	(n, m) = invr()
	s = input()
	d = {}
	for i in range(n):
		d[i + 1] = s[i]
	g = defaultdict(list)
	ind = [0 for _ in range(n + 1)]
	for _ in range(m):
		(x, y) = invr()
		g[x].append(y)
		ind[y] += 1
	q = []
	dp = [[0 for _ in range(27)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			dp[i][change(d[i])] = 1
	for i in q:
		for j in g[i]:
			for k in range(26):
				if change(d[j]) == k:
					dp[j][k] = max(dp[i][k] + 1, dp[j][k])
				else:
					dp[j][k] = max(dp[i][k], dp[j][k])
			ind[j] -= 1
			if ind[j] == 0:
				q.append(j)
	if check(ind):
		print(-1)
	else:
		ans = 0
		for i in dp:
			for j in i:
				ans = max(ans, j)
		print(ans)
t = 1
for _ in range(t):
	solve()


from collections import deque
import sys
input = sys.stdin.readline

def zero_func(nums):
	l = []
	for i in range(nums):
		k = []
		for j in range(0, 26):
			k.append(0)
		l.append(k)
	return l

def degue_func(nums1, check):
	q = deque()
	for i in range(nums1):
		if check[i] == 0:
			q.append(i)
	return q

def beauty(n, m, s, x, y):
	Degree = [0] * n
	graph = {i: [] for i in range(n)}
	c = 0
	for i in range(m):
		x[i] -= 1
		y[i] -= 1
		graph[x[i]].append(y[i])
		Degree[y[i]] += 1
	check = Degree
	check_ans = degue_func(n, check)
	ans = zero_func(n)
	while c < n and check_ans:
		a = check_ans.popleft()
		c += 1
		ans[a][ord(s[a]) - 97] += 1
		for i in graph[a]:
			for j in range(0, 26):
				ans[i][j] = max(ans[i][j], ans[a][j])
			Degree[i] -= 1
			if Degree[i] == 0:
				check_ans.append(i)
	if c != n:
		return -1
	else:
		result = 0
		for i in range(n):
			result = max(result, max(ans[i]))
		return result
(n1, m1) = map(int, input().split())
s1 = input()
listX = []
listY = []
for t in range(m1):
	(x1, y1) = map(int, input().split())
	listX.append(x1)
	listY.append(y1)
x = beauty(n1, m1, s1, listX, listY)
print(x)


from collections import deque
import sys
input = sys.stdin.readline

def beauty(n, m, s, x, y):
	deg = [0 for i in range(n)]
	graph = {i: [] for i in range(n)}
	c = 0
	for i in range(m):
		x[i] -= 1
		y[i] -= 1
		graph[x[i]].append(y[i])
		deg[y[i]] += 1
	q = deque()
	for i in range(n):
		if deg[i] == 0:
			q.append(i)
	l = []
	for i in range(n):
		k = []
		for j in range(26):
			k.append(0)
		l.append(k)
	while c < n and q:
		a = q.popleft()
		c += 1
		l[a][ord(s[a]) - 97] += 1
		for i in graph[a]:
			for j in range(26):
				l[i][j] = max(l[i][j], l[a][j])
			deg[i] -= 1
			if deg[i] == 0:
				q.append(i)
	if c != n:
		return -1
	else:
		result = 0
		for i in range(n):
			result = max(result, max(l[i]))
		return result
(n, m) = map(int, input().split())
s = input()
x = []
y = []
for _ in range(m):
	(a, b) = map(int, input().split())
	x.append(a)
	y.append(b)
print(beauty(n, m, s, x, y))


from collections import defaultdict, deque, Counter
import sys
import bisect
import math
input = sys.stdin.readline
mod = 1000000007
(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
dp = [[0 for i in range(26)] for i in range(n)]
while count < n and q:
	x = q.popleft()
	count += 1
	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)


from collections import deque
(n, m) = map(int, input().split())
s = input()
graph = [[] for i in range(n)]
freq = [[0] * 26 for i in range(n)]
degree = [0] * n
degree[0] = 0
for i in range(m):
	(x, y) = map(int, input().split())
	graph[x - 1].append(y - 1)
	degree[y - 1] += 1
d = deque()
for i in range(n):
	if degree[i] == 0:
		d.append(i)
		freq[i][ord(s[i]) - 97] += 1
c = 0
m = 1
while d:
	c += 1
	x = d.popleft()
	for i in graph[x]:
		for j in range(26):
			freq[i][j] = max(freq[i][j], freq[x][j])
		degree[i] -= 1
		if degree[i] == 0:
			freq[i][ord(s[i]) - 97] += 1
			for j in range(26):
				m = max(m, freq[i][j])
			d.append(i)
if c != n:
	print(-1)
else:
	print(m)


import sys
from collections import deque
input = sys.stdin.readline

def topological_sort(s, graph, degree, dp):
	queue = deque()
	for i in range(n):
		if degree[i] == 0:
			queue.append(i)
	count = 0
	while count < n and queue:
		count += 1
		node = queue.popleft()
		dp[node][ord(s[node]) - 97] += 1
		for i in graph[node]:
			for j in range(26):
				dp[i][j] = max(dp[i][j], dp[node][j])
			degree[i] -= 1
			if degree[i] == 0:
				queue.append(i)
	return count

def solve(n, m, s):
	graph = [[] for _ in range(n)]
	degree = [0 for _ in range(n)]
	dp = [[0 for _ in range(26)] for _ in range(n)]
	for i in range(m):
		(a, b) = map(lambda x: int(x) - 1, input().split())
		graph[a].append(b)
		degree[b] += 1
	if topological_sort(s, graph, degree, dp) != n:
		return -1
	else:
		result = 0
		for i in dp:
			result = max(result, max(i))
		return result
(n, m) = map(int, input().split())
s = list(input())
print(solve(n, m, s))


from sys import stdin
input = lambda : stdin.readline().strip()
from collections import deque
(nodes, edges) = map(int, input().split())
input_string = input()
x = []
y = []
for i in range(edges):
	(a, b) = map(int, input().split())
	x.append(a)
	y.append(b)

def beauty(nodes, edges, input_string, x, y):
	string = list(input_string)
	degree = [0 for i in range(nodes)]
	graph = {i: [] for i in range(nodes)}
	for i in range(edges):
		(a, b) = (x[i], y[i])
		a -= 1
		b -= 1
		graph[a].append(b)
		degree[b] += 1
	q = deque()
	for i in range(nodes):
		if degree[i] == 0:
			q.append(i)
	count = 0
	ans = 0
	dp_table = [[0 for i in range(26)] for i in range(nodes)]
	while count < nodes and q:
		x = q.popleft()
		count += 1
		dp_table[x][ord(string[x]) - 97] += 1
		for i in graph[x]:
			for j in range(26):
				dp_table[i][j] = max(dp_table[i][j], dp_table[x][j])
			degree[i] -= 1
			if degree[i] == 0:
				q.append(i)
	if count != nodes:
		print(-1)
	else:
		ans = 0
		for i in range(nodes):
			ans = max(ans, max(dp_table[i]))
		print(ans)
beauty(nodes, edges, input_string, x, y)


from collections import defaultdict, deque
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
arr = list(input())
q = deque()
res = 0
dg = [0 for i in range(n)]
cnt = 0
gp = defaultdict(list)
for i in range(m):
	(l, k) = map(int, input().split())
	l = l - 1
	k = k - 1
	gp[l].append(k)
	dg[k] = dg[k] + 1
mt = [[0 for i in range(26)] for i in range(n)]
for i in range(n):
	if dg[i] == 0:
		q.append(i)
while cnt < n and q:
	t = q.popleft()
	cnt = cnt + 1
	mt[t][ord(arr[t]) - 97] += 1
	for i in gp[t]:
		for j in range(26):
			mt[i][j] = max(mt[i][j], mt[t][j])
		dg[i] -= 1
		if dg[i] == 0:
			q.append(i)
if cnt != n:
	print(-1)
else:
	for i in range(0, n):
		res = max(res, max(mt[i]))
	print(res)


from sys import stdin, stdout
from collections import deque

def beauty(n, m, s, x, y):
	l = list(s)
	D = [0 for _ in range(n)]
	G = {_: [] for _ in range(n)}
	for _ in range(m):
		(a, b) = (x[_], y[_])
		a -= 1
		b -= 1
		G[a].append(b)
		D[b] += 1
	q = deque()
	for _ in range(n):
		if D[_] == 0:
			q.append(_)
	c = 0
	ans = 0
	DP = [[0 for _ in range(26)] for _ in range(n)]
	while c < n and q:
		x = q.popleft()
		c += 1
		DP[x][ord(l[x]) - 97] += 1
		for _ in G[x]:
			for __ in range(26):
				DP[_][__] = max(DP[_][__], DP[x][__])
			D[_] -= 1
			if D[_] == 0:
				q.append(_)
	if c != n:
		print(-1)
	else:
		for _ in range(n):
			ans = max(ans, max(DP[_]))
		print(ans)
(n, m) = [int(_) for _ in stdin.readline().split()]
s = input()
(x, y) = ([], [])
for _ in range(m):
	(a, b) = map(int, stdin.readline().strip().split())
	x.append(a)
	y.append(b)
beauty(n, m, s, x, y)


from collections import defaultdict, deque
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = input()
d = defaultdict(list)
degree = [0 for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	d[a - 1].append(b - 1)
	degree[b - 1] += 1
q = deque()
for i in range(n):
	if degree[i] == 0:
		q.append(i)
dp = [[0 for i in range(26)] for j in range(n)]
c = 0
while q:
	p = q.popleft()
	dp[p][ord(s[p]) - ord('a')] += 1
	c += 1
	for i in d[p]:
		for j in range(26):
			dp[i][j] = max(dp[i][j], dp[p][j])
		degree[i] -= 1
		if degree[i] == 0:
			q.append(i)
if c != n:
	print(-1)
else:
	ans = 0
	for i in range(n):
		ans = max(ans, max(dp[i]))
	print(ans)


from collections import defaultdict
import sys
from sys import stdin

def check(a):
	for i in a:
		if i:
			return True
	return False

def change(x):
	return ord(x) - ord('a')

def solve():
	(n, m) = map(int, stdin.readline().split())
	s = input()
	d = {}
	for i in range(n):
		d[i + 1] = s[i]
	g = defaultdict(list)
	ind = [0 for _ in range(n + 1)]
	for _ in range(m):
		(x, y) = map(int, stdin.readline().split())
		g[x].append(y)
		ind[y] += 1
	q = []
	dp = [[0 for _ in range(27)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			dp[i][change(d[i])] = 1
	for i in q:
		for j in g[i]:
			for k in range(26):
				if change(d[j]) == k:
					dp[j][k] = max(dp[i][k] + 1, dp[j][k])
				else:
					dp[j][k] = max(dp[i][k], dp[j][k])
			ind[j] -= 1
			if ind[j] == 0:
				q.append(j)
	if check(ind):
		print(-1)
	else:
		ans = 0
		for i in dp:
			for j in i:
				ans = max(ans, j)
		print(ans)
t = 1
for _ in range(t):
	solve()


from collections import deque
import sys
input = sys.stdin.readline
(n, m) = map(int, input().strip().split())
s = input().strip()
deg = [0] * n
adj = [[] for i in range(n)]
for i in range(m):
	(x, y) = map(int, input().strip().split())
	x -= 1
	y -= 1
	adj[x].append(y)
	deg[y] += 1
q = deque()
for i in range(n):
	if deg[i] == 0:
		q.append(i)
cnt = 0
dp = [[0 for i in range(26)] for j in range(n)]
while q:
	node = q.popleft()
	dp[node][ord(s[node]) - 97] += 1
	cnt += 1
	for i in adj[node]:
		for j in range(26):
			dp[i][j] = max(dp[i][j], dp[node][j])
		deg[i] -= 1
		if deg[i] == 0:
			q.append(i)
if cnt == n:
	ans = 0
	for i in range(n):
		ans = max(ans, max(dp[i]))
	print(ans)
else:
	print(-1)


from sys import stdin
input = lambda : stdin.readline().strip()
from collections import deque
(n, m) = map(int, input().split())
s = input()
x = []
y = []
for i in range(m):
	(a, b) = map(int, input().split())
	x.append(a)
	y.append(b)

def beauty(n, m, s, x, y):
	l = list(s)
	g = {i: [] for i in range(n)}
	d = [0 for i in range(n)]
	for i in range(m):
		x[i] -= 1
		y[i] -= 1
		g[x[i]].append(y[i])
		d[y[i]] += 1
	que = deque()
	for i in range(n):
		if d[i] == 0:
			que.append(i)
	cnt = 0
	ans = 0
	dp = []
	for i in range(n):
		dp.append([0] * 26)
	s
	while cnt < n and que:
		f = que.popleft()
		cnt += 1
		dp[f][ord(l[f]) - 97] += 1
		for i in g[f]:
			for j in range(26):
				dp[i][j] = max(dp[i][j], dp[f][j])
			d[i] -= 1
			if d[i] == 0:
				que.append(i)
	if cnt == n:
		for i in range(n):
			ans = max(ans, max(dp[i]))
		print(ans)
	else:
		print(-1)
beauty(n, m, s, x, y)


import sys, math
import io, os
from collections import defaultdict as dd, deque, Counter

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')
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]
	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)


import os
import sys
from io import BytesIO, IOBase
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):
		visited[v] = True
		recStack[v] = True
		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
		recStack[v] = False
		return 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)