Матчі
ліміт часу на тест
2 seconds
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

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

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

Вихідні дані

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

Система оцінки

  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$$$ балів): без додаткових обмежень.

Приклади

Вхідні дані
3 3
1 2
2 3
1 3
Вихідні дані
2
Вхідні дані
5 10
2 4
1 2
3 4
1 3
1 5
4 5
2 3
3 5
1 4
2 5
Вихідні дані
3

Пояснення

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

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