15737번 - 일반 그래프 매칭

문제

N개의 정점과 M개의 무방향 간선으로 이루어진 그래프가 입력으로 주어질 때에, 해당 그래프에서 최대 매칭의 크기를 출력하는 프로그램을 작성하시오.

그래프 G = (V, E)(|V|=N, |E|=M)에서 매칭 T는 E의 부분 집합이며, T의 어떠한 두 원소가 같은 정점을 공유해서는 안 된다.

최대 매칭이란 그러한 매칭 중 집합의 크기가 가장 큰 것을 이르는 말이다.

입력

첫째 줄에 정점의 수를 나타내는 N(1≤N≤500)과 간선의 개수를 나타내는 M(1≤M≤124750)이 주어진다.

둘째 줄부터 M개의 줄에 걸쳐서 각 간선의 정보가 주어진다.

각 간선의 정보는 해당 간선을 이루는 서로 다른 두 정점의 번호로 구성된다.

각 정점의 번호는 1 이상 N 이하의 자연수이다.

두 정점 사이에 간선은 최대 1개임이 보장된다.

출력

첫째 줄에 최대 매칭의 크기를 출력한다.

제한

힌트