시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 4 4 80.000%

문제

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

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

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

입력

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

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

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

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

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

출력

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

예제 입력 1

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

예제 출력 1

5

예제 입력 2

5 4
1 5
4 2
2 1
4 3

예제 출력 2

2

출처