08. Подстрока#

📝 Условие#

В вершинах ориентированного графа записаны буквы. Ценность пути — максимальная частота одной буквы на нём. Найдите наибольшую ценность или -1, если она может быть бесконечной.

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

В первой строке два числа n и m (1 ≤ n, m ≤ 3·10⁵). Во второй — строка s из n строчных букв (буква i-й вершины). Далее m строк x y — ориентированное ребро. Возможны петли и кратные рёбра.

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

Одно число — наибольшая ценность пути или -1, если она может быть сколь угодно большой.

🧪 Тесты#

Тест 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

Заметка

Оригинальное условие и проверка решения на всех тестах — по ссылке на источник.

💡 Подсказка#

⬅️ К списку задач уровня