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

Железная дорога

Железная дорога

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

Как это ни странно, но у нас в стране принято сначала делать, а потом думать. Так же и в этот раз: Минтранс издал приказ создать в стране железнодорожную сеть, и тут же буквально за месяц вся страна покрылась рельсами. Естественно, решили сэкономить и не стали проводить более одной колеи между двумя городами. И вот уже все было готово для того, чтобы пустить первый поезд, как в дело вступили СБ и МЧС. Они же постановили, что в целях безопасности по каждому пути поезда будут ходить всегда в одном направлении, и что в наших интересах как можно скорее определить, в каком. Таким образом, встала серьезная проблема - назначить каждому железнодорожному пути, соединяющему непосредственно два города, одно из двух возможных направлений. При этом в Минтрансе захотели так назначить направления, чтобы можно было пустить как можно больше поездов в этой новой системе железных дорог. Между двумя городами можно пустить не более одного поезда и только в том случае, если из одного города можно попасть в другой и вернуться обратно с учетом направлений железнодорожных путей.

Вам дан план железнодорожных путей. Требуется вывести только максимальное количество поездов, которые можно пустить при оптимальном выборе направлений. Направления определять не надо - все-таки в министерстве транспорта работают достойные люди - они это сделают сами.

Giriş verilənləri

В первой строке даны два числа N и K (1N10000, 0K100000) - количество городов и построенных железнодорожных путей соответственно. В следующих K строках по два числа A и B (1A, BN) - номера городов, между которыми была построена прямая дорога.

Çıxış verilənləri

В единственной строке вывести максимальное количество запущенных поездов.

Nümunə

Giriş verilənləri #1
6 7
1 2
2 3
3 1
4 5
5 6
6 4
3 4
Çıxış verilənləri #1
6
Müəllif А. Миланин