Корови Фермера Джона з'їдають на сніданок по ящику зерна!

На ферму надійшли \(M\) різних типів зерна \((2\le M\le 10^5)\). На жаль, є тільки один ящик зерна кожного типу. Кожна з \(N\) корів \((1\le N\le 10^5)\) має перший і другий улюблені типи зерна.

Коли корові приходить час вибирати, вона виконує такий процес:

• Якщо ящик із її улюбленим типом ще є, вона бере його і відходить
• Інакше якщо ящик із її другим улюбленим типом зерна ще є, вона бере його і відходить
• Інакше вона не бере нічого

Визначте мінімальну кількість корів, які залишаться голодними за оптимального порядку вибору. Виведіть будь-яку перестановку з \(N\) корів (порядок), за якої досягається цей мінімум.

Формат вхідних даних

Перший рядок містить два розділені пропуском цілих числа \(N\) і \(M.\)

Для кожного \(1\le i\le N,\) \(i\)-ий рядок містить два розділені пробілом цілих числа \(f_i\) і \(s_i\) (\(1\le f_i,s_i\le M\) і \(f_i\neq s_i\)) які позначають номери типів першого та другого улюбленого зерна \(і\)-ої корови.

Формат вихідних даних

Виведіть мінімальну кількість корів, які підуть голодними, за якою слідує будь-яка перестановка \(1\ldots N\), при якій досягається цей мінімум.

Приклад вхідних даних

8 10
2 1
3 4
2 3
6 5
7 8
6 7
7 5
5 8

Приклад вихідних даних

1
1
3
2
8
4
6
5
7

У цьому прикладі є \(8\) корів та \(10\) типів зерна.

Зауважимо, що ми можемо ефективно вирішити завдання для перших трьох корів незалежно від останніх п'яти, оскільки вони не мають спільних типів зерна.

Якщо для перших трьох корів встановити порядок \([1,2,3]\), то корова \(1\) вибере зерно \(2\), корова \(2\) вибере зерно \(3\), і корова \(3\) піде голодною.

Якщо для перших трьох корів встановити порядок \([1,3,2]\), то корова \(1\) вибере зерно \(2\), корова \(3\) вибере зерно \(3\), і корова \(2\) вибере зерно \(4\); і жодна корова не піде голодною.

Існують і інші перестановки, в яких жодна з трьох корів не піде голодною. Наприклад \([3,1,2]\).

Можна показати, що для останніх 5 корів як мінімум одна з корів піде голодною.

ОЦІНЮВАННЯ:

• У 4 із 14 тестів, N,M≤100.
• у 10 із 14 тестів немає додаткових обмежень.

Автор: Dhruv Rohatgi