Антон винайшов новий командний вид спорту — вотербол (як пейнтбол, тільки з водою). Він захотів поділитись своїм винаходом і покликав друзів. В Антона прекрасні відносини з усіма друзями, проте, не факт, що між собою друзі мають такі ж. А саме, ми знаємо, що друг номер a_i конфліктує з другом b_i.
Антону дали записані конфліктних пар (a_i;b_i). І от наче, можна було б поділити гравців на дві команди, але так просто в Антона не буває...
Він хоче взяти розбити ці конфліктні пари на відрізки так, щоб
кожна конфліктна пара належала рівно до одного відрізку;
якщо враховувати тільки відносини на кожному відрізку окремо, то можна розбити всіх людей на дві команди так, щоб не було двох людей, що конфліктують між собою, та знаходяться в одній команді.
Наприклад, нехай у нас є масив конфліктних пар [(1, 2), (2, 3), (1, 3)]. Ми можемо взяти перші дві пари у перший відрізок. У такому випадку ми зможемо зробити команди: та . У другий відрізок ми можемо взяти останню пару. та мають бути в різних команда, а може бути у будь-якій команді. Альтернативно, ми можемо віднести першу пару до першого відрізку, а останні два до другого. Зверніть увагу, що ми не можемо віднести першу та третю пару до одного відрізку, а другу пару до іншого. Причиною цього є те, що відрізок має містити лише послідовні пари. Ми також не можемо віднести всі пари до одного відрізку, бо тоді у будь-якому випадку буде команда, у якій люди конфліктують.
Антон знову перемудрив з умовами, і тепер не може розв'язати задачу. Допоможіть йому, і скажіть мінімальну кількість відрізків, на які він може розбити пари, щоб виконувались умови вище.
Перший рядок містить два цілі числа , (1 \le n, m \le 10^6) — кількість друзів та недружніх відносин серед друзів.
Наступні рядків містять по два цілі числа a_i, b_i (1 \le a_i, b_i \le n, a_i \neq b_i), що означають, що a_i-й друг конфліктує з b_i-м.
Гарантується, що жодна пара () не повторюється більше ніж один раз.
Виведіть одне ціле число — відповідь на задачу.
Приклад
Приклад 1
Перший приклад пояснений в легенді вище.
У другому прикладі, можна, наприклад, розбити на наступні відрізки: , , .
На першому відрізку можна утворити команди , [2,3,5] — і не конфліктують між собою, як і пари , , .
На другому відрізку можна утворити команди , [2,4,5] — і не конфліктують між собою, як і пари , , .
На третьому відрізку можна утворити команди , [3,4,5] — і не конфліктують між собою, як і пари , , .
( бали): n \le 3;
( балів): n \le 10;
( балів): n, m \le 5000;
( балів): пари конфліктуючих друзів у вхідних даних згенеровано випадково; це значить, що було вибрано випадковим чином пар з усіх \frac{n (n-1)}{2} пар;
( балів): кожна людина конфліктує не більше, ніж з людьми;
( балів): n \le 10^5;
( балів): n \le 2 \cdot 10^5;
( балів): без додаткових обмежень.