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