|
Слабая K-связность
(Время: 1 сек. Память: 16 Мб Сложность: 47%)
Ане, как будущей чемпионке мира по программированию, поручили очень ответственное задание. Правительство вручает ей план постройки дорог между N городами. По плану все дороги односторонние, но между двумя городами может быть больше одной дороги, возможно, в разных направлениях. Ане необходимо вычислить минимальное такое K, что данный ей план является слабо K-связным.
Правительство называет план слабо K-связным, если выполнено следующее условие: для любых двух различных городов можно проехать от одного до другого, нарушая правила движения не более K раз. Нарушение правил - это проезд по существующей дороге в обратном направлении. Гарантируется, что между любыми двумя городами можно проехать, возможно, несколько раз нарушив правила.
Входные данные
В первой строке входного файла INPUT.TXT записаны два числа 2 ≤ N ≤ 300 и 1 ≤ M ≤ 105 - количество городов и дорог в плане. В последующих M строках даны по два числа - номера городов, в которых начинается и заканчивается соответствующая дорога.
Выходные данные
В выходной файл OUTPUT.TXT выведите минимальное K, такое, что данный во входном файле план является слабо K-связным.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 2
1 2
1 3
| 1 |
| 2 | 4 4
2 4
1 3
4 1
3 2
| 0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
