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