Петро хоче скористатись своїм власним алгоритмом, щоб розв'язати дуже важливу задачу для орієнтовного графа G, який складається з n вершин та m дуг. На жаль, Петро не вміє оцінювати складність свого алгоритму. Він лише знає, що вона пов'язана з порядком зростання величини F(n), яка позначає кількість шляхів довжини n з вершини s у вершину t в графі G. Петро хоче обмежити F(n) многочленом мінімальної степені, тобто знайти таке мінімальне невід'ємне ціле число k, що для деякої константи C нерівність F(n) ≤ C * nk буде виконуватись для усіх додатних n.

Допоможіть йому це зробити.

Вхідні дані

У першому рядку записано чотири числа: n, m, s, t (1 ≤ n, m ≤ 105). Вершини графа пронумеровано числами від 1 до n. У кожному з наступних m рядків через пропуск записано два числа - номери початкової та кінцевої вершини чергової дуги. У графі не може бути кратних дуг, але можуть бути петлі.

Вихідні дані

Виведіть мінімальне ціле число k, яке задовольняє умові задачі. Якщо таких чисел не існує, виведіть "-1".