Codeforces Round 460 (Div. 2) |
---|
Закончено |
Дан граф из $$$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$$$ раза.
Название |
---|