Антон винайшов новий командний вид спорту — вотербол (як пейнтбол, тільки з водою). Він захотів поділитись своїм винаходом і покликав $$$n$$$ друзів. В Антона прекрасні відносини з усіма друзями, проте, не факт, що між собою друзі мають такі ж. А саме, ми знаємо, що друг номер $$$a_i$$$ конфліктує з другом $$$b_i$$$.
Антону дали записані $$$m$$$ конфліктних пар ($$$a_i;b_i$$$). І от наче, можна було б поділити гравців на дві команди, але так просто в Антона не буває...
Він хоче взяти розбити ці $$$m$$$ конфліктні пари на відрізки так, щоб
Наприклад, нехай у нас є масив конфліктних пар $$$[(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$$$) не повторюється більше ніж один раз.
Виведіть одне ціле число — відповідь на задачу.
3 31 22 31 3
2
5 102 41 23 41 31 54 52 33 51 42 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)$$$.