Дан граф из n вершин и m ориентированных ребер. В каждой вершине записана некоторая строчная латинская буква.
Определим величину пути как наибольшее количество раз, которое какая-то буква встречалась на этом пути. Например, если буквы на пути образуют строку «abaca», то величина этого пути равна 3.
Ваша задача — найти путь с наибольшей величиной.
Входные данные:
Первая строка содержит два целых числа n, m (1 ≤ n, m ≤ 200000), означающих, что в графе n вершин и m ориентированных ребер.
Вторая строка содержит строку s, состоящую только из строчных латинских букв. Символ номер i — это буква, записанная в вершине номер i.
Далее следуют m строк. Каждая из этих строк содержит два целых числа x, y (1 ≤ x, y ≤ 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 |