Дан граф из \(n\) вершин и \(m\) ориентированных ребер. В каждой вершине записана некоторая строчная латинская буква. Определим величину пути как наибольшее количество раз, которое какая-то буква встречалась на этом пути. Например, если буквы на пути образуют строку «abaca», то величина этого пути равна \(3\). Ваша задача — найти путь с наибольшей величиной.
Выходные данные
Выведите одно число — максимальную величину пути. Если существуют пути со сколь угодно большой величиной, выведите -1.
Примечание
В первом примере путь с максимальной величиной — это \(1 \to 3 \to 4 \to 5\). Величина этих путей равна \(3\), т. к. буква «a» встречается \(3\) раза.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
abaca
1 2
1 3
3 4
4 5
|
3
|
|
2
|
6 6
xzyabc
1 2
3 1
2 3
5 4
4 3
6 4
|
-1
|
|
3
|
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
|