Матчі#271

Матчі

2 секунди
256 мегабайтів
Складна

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

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

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

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

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

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

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

Вхідні дані

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

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

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

Вихідні дані

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

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

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

У другому прикладі, можна, наприклад, розбити на наступні відрізки: , , .

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

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

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

Оцінювання

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

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

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

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

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

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

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

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