eolymp
bolt
Try our new interface for solving problems
Məsələlər

Слабая k-связность

Слабая k-связность

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Ане, как будущей чемпионке мира по программированию, поручили очень ответственное задание. Правительство Н-ской области вручает ей план постройки дорог между городами. По плану все дороги односторонние, но между двумя городами может быть больше одной дороги, возможно, в разных направлениях. Ане необходимо вычислить минимальное такое k, что данный ей план является слабо k-связным.

Правительство называет план слабо k-связным, если выполнено следующее условие: для любых двух различных городов можно проехать от одного до другого, нарушая правила движения не более k раз. Нарушение правил - это проезд по существующей дороге в обратном направлении. Гарантируется, что между любыми двумя городами можно проехать, возможно, несколько раз нарушив правила.

Giriş verilənləri

В первой строке входного файла даны два числа 2n300 и 1m10^5 - количество городов и дорог в плане. В последующих m строках даны по два числа - номера городов, в которых начинается и заканчивается соответствующая дорога.

Çıxış verilənləri

В выходной файл выведите минимальное k, такое, что данный во входном файле план является слабо k-связным.

Nümunə

Giriş verilənləri #1
3 2
1 2
1 3
Çıxış verilənləri #1
1