PKU 1422. Air Raid

공습

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 2879	Accepted: 1701

설명

어떤 도시가 있는데, 이 도시의 모든 도로는 일방통행이고 각 도로는 서로 다른 교차로와 연결되어있습니다. 또한 이 길들은 아무리 길을 따라 걸어도 한 번 출발했던 교차로로 다시 돌아올 수 없는, 순환하지 않는 길들입니다.

이러한 가정 하에 당신은 프로그램을 작성하여 만약 낙하부대가 이 도시에 작전을 펼쳤을 때 모든 낙하부대원은 하나 이상의 교차로를 지나야만 하고, 모든 교차로를 한 명 이상의 낙하부대원이 지나가도록 하는 최소한의 낙하부대원 수를 구해야 합니다. 모든 낙하부대원들은 교차로에 착지한 후 도시의 길을 따라 다른 교차로를 찾아갈 수 있습니다. 각 낙하부대원들의 시작지점이 될 교차로에는 제한이 없습니다.

입력

당신의 프로그램은 데이터의 셋들을 읽어야 합니다. 입력의 첫 줄은 데이터 셋의 총 개수를 나타냅니다. 각 데이터 셋은 도시의 구조를 나타냅니다:

no_of_intersections 
no_of_streets 
S1 E1 
S2 E2 
...... 
Sno_of_streets Eno_of_streets 

각 데이터 셋의 첫번째 줄은 양정수 no_of_intersections ( 0보다 크고 120보다 작거나 같습니다.)로 교차로의 개수를 나타냅니다. 두번째 줄은 양정수 no_of_streets 로 도시에 있는 길의 개수를 나타냅니다. 그 다음에 오는건 no_of_streets 개수의 줄로 각 줄은 무작위 순서로 도시의 길이 어떻게 이어져있는지를 나타냅니다. 길의 수 k (k <= no_of_street) 에 따라 정해진 줄들은 두 개의 양정수로 이루어져있는데, 두 양정수 사이엔 공백을 둡니다: Sk(1 <= Sk <= no_of_intersections) - 길의 시작지점에 있는 교차로의 번호  와 Ek(1 <= Ek <= no_of_intersections) - 길의 종착지점에 있는 교차로의 번호 가 두 양정수입니다. 교차로들은 1부터 no_of_intersections 까지의 정수로 나타냅니다.

연속된 데이터 셋들 사이에는 공란은 없습니다. 입력 데이터는 정확합니다.(??)

출력

프로그램의 결과는 정해진 출력방식을 따라야 합니다. 각 입력 데이터 셋에 대해 하나의 줄로 결과를 출력하는데, 출력값은 하나의 정수로 나타나며, 도시의 모든 교차로를 가기 위해 필요한 최소한의 낙하부대원 수를 나타냅니다.

입력 예시

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

출력 예시

2
1

Source

Dhaka 2002


p.s: Input data are correct. 이부분은 뭘로 해석할까요?..왜 저기 들어가있는거지..OTL
p.s2: Mr.K 의 지적을 받아 수정하였습니다.