Сейчас зима, во всех смыслах. И лишь воспоминания о прошедшем заставляют трезво смотреть на вещи.
— Неужели это конец? — Кто знает... — Ну тогда скорее к делу!
Дан неориентированный граф без петель и кратных ребер. Найти величину максимального паросочетания, то есть максимальный размер подможества P ребер графа, что любой вершине инцидентно не более одного ребра из P.
В первой строке даны два числа N (1 ≤ N ≤ 400) и K (0 ≤ K ≤ N·(N-1)/2) — количество вершин и ребер в графе. Каждая из следующих K строк содержит по два числа u и v — описание одного ребра. Гарантируется, что граф вполне случайный.
Вывести единственное число — величину максимального паросочетания.