문제 156
일반 그래프의 최대 매칭
정점이 $N$개이고 간선이 $M$개인 무방향 단순 그래프가 주어진다. 정점의 번호는 $0$부터 $N-1$까지이다.
서로 정점을 공유하지 않는 간선들을 선택하려고 한다. 선택할 수 있는 간선 수의 최댓값을 구해 보자.
입력
첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $Q$가 주어진다. $(1 \le Q \le 100)$
각 테스트 케이스의 첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 400; 0 \le M \le N(N-1)/2)$
두 번째 줄부터 $M$개의 줄에 걸쳐 간선의 양 끝 정점 번호 $u$, $v$가 공백으로 구분되어 주어진다. $(0 \le u, v < N; u \ne v)$ 같은 무방향 간선은 두 번 주어지지 않는다.
전체 테스트 케이스에서 $N$의 합은 $800$ 이하이고 $M$의 합은 $300\,000$ 이하이다.
출력
각 테스트 케이스마다 선택할 수 있는 간선 수의 최댓값을 한 줄에 출력한다.
예제 입력 1
3 5 6 0 1 0 2 0 4 1 2 1 3 2 4 5 3 0 2 1 2 2 3 4 4 0 1 0 2 0 3 2 3
예제 출력 1
2 1 2