Всім відомо, що позаминулого століття ковбої займалися перегоном худоби. Перегін худоби завжди вважався небезпечною справою. Ковбой Джон, готуючись до перегону, вивчав план місцевості. Так як місцевість гориста, то дістатися з одного поселення в інше можна тільки дорогами, можливо через інші поселення. Головною небезпекою на шляху були бандити, які мешкають у різних населених пунктах, та організуючі угруповання для нападу на ковбоїв. Щоб роз'єднати їх, Джон розробив геніальний план повної ізоляції поселень один від одного

Порадившись з напарниками, Джон прийшов до висновку, що тимчасово дороги можна вивести з ладу, влаштувавши каменепад. Вночі можна проїхати дорогою, встати посередині і влаштувати каменепад (але назад цією дорогою вже не вийде повернутись, лише вперед)

Сам Джон цього зробити не може, тільки він знає таємничі стежки і повинен переганяти отару. Тому він вирішив використовувати найманців. Найманці є в будь-якому місті і в будь-якій кількості, але за кожного з них необхідно платити певну суму. Тому Джон хоче витратити якомога менше грошей. Допоможіть Джону визначити мінімальну кількість найманців, які зможуть вивести з ладу абсолютно всі дороги (влаштувавши каменепад на кожній дорозі).

Формат вхідних даних

У першому рядку кожного тесту знаходяться два цілих невід'ємних числа \(N\) (\(0 < N < 1000\)) – кількість поселень та \(M\) \((0 ≤ M ≤ 100 000)\) – кількість доріг, що їх з'єднують.

Далі слідує \(M\) рядків, що містять опис доріг. У \(i\)-му рядку знаходяться два натуральні числа \(V\) і \(U\) \((1 ≤ V, U ≤ N)\) – номери поселень, які з'єднує i дорога. Між двома різними поселеннями існує не більше однієї дороги, але може існувати кілька маршрутів. Немає доріг, які утворюють петлю, що виходить із поселення і веде до нього ж, не заходячи в інші поселення. Не гарантується, що існує маршрут між будь-якою парою поселень. Маршрутом називається така послідовність поселень \(s_1-s_2- … -s_n\), що будь-які два послідовні поселення \(s_i\) і \(s_{i+1}\) з'єднані дорогою.

Формат вихідних даних

Виведіть мінімальну кількість найманців, необхідну для ізоляції всіх поселень.

Приклад вхідних даних

6 6
1 2
2 3
1 3
4 5
5 6
4 6

Приклад вихідних даних

2