Сложность алгоритма
Петя хочет воспользоваться своим собственным алгоритмом, чтобы решить очень важную задачу для ориентированного графа G, состоящего из n вершин и m ребер. К сожалению, Петя не умеет оценивать сложность своего алгоритма. Он лишь знает, что она связана с порядком роста величины F(n), которая обозначает количество путей длины n из вершины s в вершину t в графе G. Петя хочет ограничить F(n) многочленом минимальной степени, то есть найти такое минимальное неотрицательное целое число k, что для некоторой константы C неравенство F(n) ≤ C * n^k будет выполняться для всех положительных n.
Помогите ему сделать это.
Входные данные
В первой строке записаны четыре числа: n, m, s, t (1 ≤ n, m ≤ 10^5). Вершины графа занумерованы числами от 1 до n. В каждой из следующих m строк через пробел записаны два числа - номера начальной и конечной вершины очередной дуги. В графе не может быть кратных дуг, но могут быть петли.
Выходные данные
Выведите минимальное целое число k, удовлетворяющее условию задачи. Если таких чисел не существует, выведите "-1".