Складність алгоритму#4342
Петро хоче скористатись своїм власним алгоритмом, щоб розв'язати дуже важливу задачу для орієнтованого графа , який складається з вершин та дуг. На жаль, Петро не вміє оцінювати складність свого алгоритму. Він лише знає, що вона пов'язана з порядком зростання величини , яка позначає кількість шляхів довжини з вершини у вершину в графі . Петро хоче обмежити многочленом мінімальної степені, тобто знайти таке мінімальне невід'ємне ціле число , що для деякої константи нерівність F(n) \le C \cdot n^k буде виконуватись для усіх додатних .
Допоможіть йому це зробити.
У першому рядку записано чотири числа: , , , (1 \le n, m \le 10^5). Вершини графа пронумеровано числами від до . У кожному з наступних рядків через пропуск записано два числа - номери початкової та кінцевої вершини чергової дуги. У графі не може бути кратних дуг, але можуть бути петлі.
Виведіть мінімальне ціле число , яке задовольняє умові задачі. Якщо таких чисел не існує, виведіть "".
Приклад 1
Приклад 2