ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU contest. Petrozavodsk training camp. Winter 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Сложность алгоритма

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Петя хочет воспользоваться своим собственным алгоритмом, чтобы решить очень важную задачу для ориентированного графа G, состоящего из n вершин и m дуг. К сожалению, Петя не умеет оценивать сложность своего алгоритма. Он лишь знает, что она связана с порядком роста величины F(N), которая обозначает количество путей длины N из вершины s в вершину t в графе G. Петя хочет ограничить F(N) многочленом минимальной степени, то есть найти такое минимальное неотрицательное целое число k, что для некоторой константы C неравенство F(N) ≤ CNk будет выполняться для всех положительных N. Помогите ему сделать это.

Исходные данные

В первой строке через пробел записаны 4 числа: n, m, s, t (1 ≤ n, m ≤ 100000). Вершины графа занумерованы числами от 1 до n. В каждой из следующих m строк через пробел записаны два числа — номера начальной и конечной вершины очередной дуги. В графе не может быть кратных дуг, но могут быть петли.

Результат

Выведите минимальное целое число k, удовлетворяющее условию задачи. Если таких чисел не существует, выведите «−1».

Примеры

исходные данныерезультат
2 3 1 2
1 1
1 2
2 2
1
3 6 1 2
1 2
2 1
1 3
3 1
2 3
3 2
-1
Автор задачи: Иван Бурмистров
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, February 2009
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1691. Сложность алгоритма