Матчі

Антон винайшов новий командний вид спорту — вотербол (як пейнтбол, тільки з водою). Він захотів поділитись своїм винаходом і покликав $n$ друзів. В Антона прекрасні відносини з усіма друзями, проте, не факт, що між собою друзі мають такі ж. А саме, ми знаємо, що друг номер $a_i$ конфліктує з другом $b_i$.

Антону дали записані $m$ конфліктних пар ($a_i;b_i$). І от наче, можна було б поділити гравців на дві команди, але так просто в Антона не буває...

Він хоче взяти розбити ці $m$ конфліктні пари на відрізки так, щоб

1. кожна конфліктна пара належала рівно до одного відрізку;

2. якщо враховувати тільки відносини на кожному відрізку окремо, то можна розбити всіх людей на дві команди так, щоб не було двох людей, що конфліктують між собою, та знаходяться в одній команді.

Наприклад, нехай у нас є масив конфліктних пар $[(1,2),(2,3),(1,3)]$. Ми можемо взяти перші дві пари у перший відрізок. У такому випадку ми зможемо зробити команди: $[1,3]$ та $[2]$. У другий відрізок ми можемо взяти останню пару. $1$ та $3$ мають бути в різних команда, а $2$ може бути у будь-якій команді. Альтернативно, ми можемо віднести першу пару до першого відрізку, а останні два до другого. Зверніть увагу, що ми не можемо віднести першу та третю пару до одного відрізку, а другу пару до іншого. Причиною цього є те, що відрізок має містити лише послідовні пари. Ми також не можемо віднести всі пари до одного відрізку, бо тоді у будь-якому випадку буде команда, у якій люди конфліктують.

Антон знову перемудрив з умовами, і тепер не може розв'язати задачу. Допоможіть йому, і скажіть мінімальну кількість відрізків, на які він може розбити пари, щоб виконувались умови вище.

Вхідні дані

Перший рядок містить два цілі числа $n$, $m$ ($1\le n,m\le 10^6$) — кількість друзів та недружніх відносин серед друзів.

Наступні $m$ рядків містять по два цілі числа $a_i$, $b_i$ ($1\le a_i,b_i\le n$, $a_i\ne b_i$), що означають, що $a_i$-й друг конфліктує з $b_i$-м.

Гарантується, що жодна пара ($a;b$) не повторюється більше ніж один раз.

Вихідні дані

Виведіть одне ціле число — відповідь на задачу.

Приклади

Примітка

Перший приклад пояснений в легенді вище.

У другому прикладі, можна, наприклад, розбити на наступні відрізки: $[1;6]$, $[7;9]$, $[10;10]$.

На першому відрізку можна утворити команди $[1,4]$, $[2,3,5]$ — $1$ і $4$ не конфліктують між собою, як і пари $(2;3)$, $(2;5)$, $(3;5)$.

На другому відрізку можна утворити команди $[1,3]$, $[2,4,5]$ — $1$ і $3$ не конфліктують між собою, як і пари $(2;4)$, $(2;5)$, $(4;5)$.

На третьому відрізку можна утворити команди $[1,2]$, $[3,4,5]$ — $1$ і $2$ не конфліктують між собою, як і пари $(3;4)$, $(3;5)$, $(4;5)$.

Оцінювання

1. ($4$ бали): $n\le 3$;

2. ($7$ балів): $n\le 10$;

3. ($15$ балів): $n,m\le 5000$;

4. ($13$ балів): пари конфліктуючих друзів у вхідних даних згенеровано випадково; це значить, що було вибрано випадковим чином $m$ пар з усіх $\frac{n(n-1)}{2}$ пар;

5. ($14$ балів): кожна людина конфліктує не більше, ніж з $10$ людьми;

6. ($19$ балів): $n\le 10^5$;

7. ($17$ балів): $n\le 2\cdot 10^5$;

8. ($11$ балів): без додаткових обмежень.