D. Подстрока
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан граф из $$$n$$$ вершин и $$$m$$$ ориентированных ребер. В каждой вершине записана некоторая строчная латинская буква. Определим величину пути как наибольшее количество раз, которое какая-то буква встречалась на этом пути. Например, если буквы на пути образуют строку «abaca», то величина этого пути равна $$$3$$$. Ваша задача — найти путь с наибольшей величиной.

Входные данные

Первая строка содержит два целых числа $$$n, m$$$ ($$$1 \leq n, m \leq 300\,000$$$), означающих, что в графе $$$n$$$ вершин и $$$m$$$ ориентированных ребер.

Вторая строка содержит строку $$$s$$$, состоящую только из строчных латинских букв. Символ номер $$$i$$$ — это буква, записанная в вершине номер $$$i$$$.

Далее следуют $$$m$$$ строк. Каждая из этих строк содержит два целых числа $$$x, y$$$ ($$$1 \leq x, y \leq n$$$), описывающих ориентированное ребро из $$$x$$$ в $$$y$$$. Обратите внимание, $$$x$$$ может быть равно $$$y$$$, и могут быть несколько ребер между $$$x$$$ и $$$y$$$. Кроме того, граф может быть несвязным.

Выходные данные

Выведите одно число — максимальную величину пути. Если существуют пути со сколь угодно большой величиной, выведите -1.

Примеры
Входные данные
5 4
abaca
1 2
1 3
3 4
4 5
Выходные данные
3
Входные данные
6 6
xzyabc
1 2
3 1
2 3
5 4
4 3
6 4
Выходные данные
-1
Входные данные
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
Выходные данные
4
Примечание

В первом примере путь с максимальной величиной — это $$$1 \to 3 \to 4 \to 5$$$. Величина этих путей равна $$$3$$$, т. к. буква «a» встречается $$$3$$$ раза.