문제
세계적인 유명인사인 재우는 일정기간 여행할 계획이다.
여행기간 동안 N개의 국가를 방문하는데 보안문제로 가능한 최소수의 비행조종사를 고용하고자 한다.
조종사들은 자신이 계약한 여행구간 하나만을 비행할 수 있는데 필요하다면 여러 번 비행할 수 있다.
고용된 조종사들은 재우가 여행하는 기간동안 항상 대기하거나 비행하고 있다.
(a, b)구간을 비행하는 조종사는 a에서 b로의 비행과 b에서 a로의 비행 모두 가능하다.
국가의 수와 비행사의 정보가 주어질때 최소수의 조종사를 구하는 프로그램을 작성하시오.
입력
첫 행에 테스트 케이스의 수 TC( 1 <= TC <= 100) 가 입력된다.
다음행부터 각 테스트 케이스 정보가 주어진다.
테스트 케이스의 첫 행에는 국가의 수 N과 조종사의 수 M이 주어진다.
이어지는 M개의 행에는 각 조종사가 비행하는 비행 정보가 주어진다.
출력
각 테스트 케이스에 대하여 재우가 고용해야 하는 비행사의 최소수를 행으로 구분하여 출력한다.
예제
2
3 3
1 2
2 3
1 3
5 4
2 1
2 3
4 3
4 5
2
4
출처
BAPC 2013 F_Flying Safely
로그인해야 코드를 작성할 수 있어요.