피난

CC동산에서 일하던 개미가 갑작스러운 재난으로 대부분 죽고, 여왕개미 1000마리와 소수의 일개미만 살아남았다. 남은 개미는 종족을 지키려고 여왕개미 일부를 피난처로 보내기로 했다. 피난처는 매우 안전해서, 몇 달만 지나면 개미 종족이 그곳에서 다시 번성한다.

피난처의 구조는 다음과 같다.

1. 피난처는 $N$개의 체크포인트와 체크포인트를 잇는 $M$개의 길로 이루어진다.
2. $x < y$이면 체크포인트 $x$의 고도가 체크포인트 $y$의 고도보다 높다.
3. 길은 언제나 고도가 높은 체크포인트에서 낮은 체크포인트로 이어진다.
4. 개미는 고도가 낮은 체크포인트에서 높은 체크포인트로 이동하지 못한다.
5. 체크포인트 $1$번에 이어진 길은 각각 개미 한 마리만 지날 수 있다.
6. 체크포인트 $N$번에 이어진 길은 각각 개미 한 마리만 지날 수 있다.
7. 두 체크포인트 $u$, $v$를 직접 잇는 길은 많아야 하나다.

$1$번에도 $N$번에도 이어지지 않은 길은 지나는 개미 수에 제한이 없고, 체크포인트에 머무는 개미 수에도 제한이 없다.

여왕개미는 모두 $1$번 체크포인트에서 출발한다. $N$번 체크포인트에 닿지 못한 여왕개미는 살아남지 못하므로, 개미들은 $N$번까지 보낼 수 있는 여왕개미 수를 최대로 하려고 한다. 나머지 여왕개미는 방어 전선에 배치한다.

피난처로 보낼 수 있는 여왕개미가 최대 몇 마리인지 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 체크포인트의 수 $N$($2 \le N \le 200$)과 길의 수 $M$($1 \le M \le N(N-1)/2$)이 주어진다.

이어지는 $M$개 줄에는 두 정수 $x$, $y$($1 \le x < y \le N$)가 주어진다. 체크포인트 $x$에서 $y$로 가는 길이 있다는 뜻이다.

각 테스트 케이스마다 $N$번 체크포인트까지 보낼 수 있는 여왕개미 수의 최댓값을 한 줄에 출력한다.