시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 449 | 221 | 187 | 52.235% |
어느 날, CC동산에 놀러온 초등학생 석주가 CC동산에 무차별적으로 침을 뱉었다. CC동산 일대에서 열심히 일하던 개미들의 90%가 석주의 침 때문에 몰살당했고, 소수 개미와 1000마리의 여왕개미만이 남게 되었다.
남은 개미들은 회의 끝에, 종족 보존을 위하여 수많은 여왕개미 중 일부 여왕개미를 피난처로 보내기로 했다. 이 피난처는 매우 안전한 피난처로, 몇 달만 지나면 개미 종족을 다시 번성에 이르게 할 수 있을 것이다.
이 피난처의 특징은 다음과 같다.
피난처의 N번 체크포인트에 도착하지 못한 개미는 석주의 침에 의해 모두 죽는다. 모든 여왕개미는 1번 체크포인트에서 여정을 시작한다.
개미들은 보낼 수 있는 최대한으로 여왕개미를 보내려고 한다. 또한, 석주의 공격에 의해 피난처가 무너지는 것을 지연시키기 위하여, 피난처에 보낼 수 있는 만큼만 여왕개미를 보내고 나머지는 방어 전선에 배치시키고자 한다.
개미들에게 최대 몇 마리의 여왕개미를 피난처로 보낼 수 있는지 알려주자.
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다.
각 테스트케이스의 첫 번째 줄에는 체크포인트의 수 N(2 ≤ N ≤ 200)과 간선의 수 M(1 ≤ M ≤ N(N-1)/2)가 주어진다.
각 테스트케이스의 두 번째 줄부터 M+1번째 줄까지 두 정수 x, y(1 ≤ x, y ≤ N)이 주어진다. 이는 x에서 y로 가는 길이 있다는 뜻이다.
각 테스트 케이스 별로 최대 몇 마리의 여왕개미를 보낼 수 있는지 출력한다.
3 7 9 1 2 1 3 1 4 1 5 2 6 3 6 4 6 5 6 6 7 12 19 1 3 1 4 1 2 1 5 2 8 3 9 3 7 4 6 4 11 5 8 6 9 6 10 7 10 7 11 8 12 9 10 9 12 10 12 11 12 4 6 1 2 1 3 1 4 2 3 2 4 3 4
1 3 3