시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 155 61 50 51.020%

문제

어느 날, CC동산에 놀러온 초등학생 석주가 CC동산에 무차별적으로 침을 뱉었다. CC동산 일대에서 열심히 일하던 개미들의 90%가 석주의 침 때문에 몰살당했고, 소수 개미와 1000마리의 여왕개미만이 남게 되었다.

남은 개미들은 회의 끝에, 종족 보존을 위하여 수많은 여왕개미 중 일부 여왕개미를 피난처로 보내기로 했다. 이 피난처는 매우 안전한 피난처로, 몇 달만 지나면 개미 종족을 다시 번성에 이르게 할 수 있을 것이다.

이 피난처의 특징은 다음과 같다.

  1. 이 피난처는 N개의 체크포인트와 체크포인트를 잇는 M개의 길로 구성되어 있다.
  2. x<y일 경우 체크포인트 x의 고도는 체크포인트 y의 고도보다 높다.
  3. 길은 항상 높은 고도의 체크포인트에서 낮은 고도의 체크포인트로 이어져 있다.
  4. 개미는 높이가 낮은 체크포인트에서 높이가 높은 체크포인트로 이동하지 못한다.
  5. 체크포인트 1번과 이어진 길은 한 마리의 개미만 이용할 수 있다.
  6. 체크포인트 N번과 이어진 길은 한 마리의 개미만 이용할 수 있다.
  7. 모든 체크포인트 u, v에 대해 체크포인트 u와 v를 직접 잇는 길은 최대 1개이다.

피난처의 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

힌트