\begin{problem}{Матчі}{standard input}{standard output}{2 seconds}{256 megabytes}

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

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

Він хоче взяти розбити ці $m$ конфліктні пари на відрізки так, щоб
\begin{enumerate}
\item кожна конфліктна пара належала рівно до одного відрізку;
\item якщо враховувати тільки відносини на кожному відрізку окремо, то можна розбити всіх людей на дві команди так, щоб не було двох людей, що конфліктують між собою, та знаходяться в одній команді.
\end{enumerate}

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

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

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

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

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

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

\Scoring
\begin{enumerate}
\item ($4$ бали): $n \le 3$;
\item ($7$ балів): $n \le 10$;
\item ($15$ балів): $n, m \le 5000$;
\item ($13$ балів): пари конфліктуючих друзів у вхідних даних згенеровано випадково; це значить, що було вибрано випадковим чином $m$ пар з усіх $\frac{n (n-1)}{2}$ пар;
\item ($14$ балів): кожна людина конфліктує не більше, ніж з $10$ людьми;
\item ($19$ балів): $n \le 10^5$;
\item ($17$ балів): $n \le 2 \cdot 10^5$;
\item ($11$ балів): без додаткових обмежень.
\end{enumerate}

\Examples

\begin{example}
\exmpfile{example.01}{example.01.a}%
\exmpfile{example.02}{example.02.a}%
\end{example}

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

У другому прикладі, можна, наприклад, розбити на наступні відрізки: $[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)$.

\end{problem}

