Дан граф из \(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.
В первом примере путь с максимальной величиной — это \(1 \to 3 \to 4 \to 5\). Величина этих путей равна \(3\), т. к. буква «a» встречается \(3\) раза.
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
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач