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

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

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