Антон винайшов новий командний вид спорту --- вотербол (як пейнтбол, тільки з водою). Він захотів поділитись своїм винаходом і покликав $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$ може бути у будь-якій команді. Альтернативно, ми можемо віднести першу пару до першого відрізку, а останні два до другого. Зверніть увагу, що ми не можемо віднести першу та третю пару до одного відрізку, а другу пару до іншого. Причиною цього є те, що відрізок має містити лише послідовні пари. Ми також не можемо віднести всі пари до одного відрізку, бо тоді у будь-якому випадку буде команда, у якій люди конфліктують.

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