Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
ORIENT
   

Задача Дорожна реформа (ORIENT)

Місто Вінниця, як і більшість міст України, має мережу доріг з двостороннім рухом по кожній з них. Ця мережа має властивість зв’язності, тобто по цих дорогах можна потрапити з довільної точки міста у довільну іншу.

Останнього часу головною проблемою на вулицях міста є автомобільні пробки. З метою підвищення пропускної здатності доріг та ліквідування заторів мер міста вирішив на деяких з них встановити одностороній рух. Ваша задача полягає у тому, щоб визначити максимальну кількість доріг, на яких можна це зробити, не порушивши зв’язності.

Технічні умовиПрограма ORIENT читає з клавіатури два цілих числа N кількість перехресть у місті та M кількість доріг (1N20000, 1M≤200000). Далі читає M рядків, у кожному з яких записано два числа номери перехресть, звязаних дорогою. Кожні два перехрестя з’єднуються не більш ніж однією дорогою.Програма виводить на екран одне число K – максимальну кількість доріг, на яких можна увести односторонній рух. Приклад:
Введення Виведення
5 62 12 32 42 54 34 5 5 

© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"