eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків

Now

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Зароз зима, у довільному змісті. І лише спогади про минуле заставляють тверезо дивитись на речі.

Невже це кінець? Хто знає... Ну тоді скоріше до справи!

Задано неориієнтовний граф без петель та кратних ребер. Знайти величину максимального паросполучення, тобто максимальний розмір підможини P ребер графа, що довільній вершині інцидентно не більше одного ребра з P.

Вхідні дані

У першому рядку задано два числа N (1N400) та K (0KN·(N-1)/2) — кількість вершин і ребер у графі. Кожен з наступних K рядків містить по два числа u і v — опис одного ребра. Гарантується, що граф цілком випадковий.

Вихідні дані

Вивести єдине число — величину максимального паросполучення.

Приклад

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