원하는 대로 불러라

교수 장은 일반 그래프에서 최장 경로 문제가 P = NP가 아니라면 다항 시간에 풀 수 없다는 이야기를 들었다. 이제 장 교수는 일부 그래프에서 이 문제를 다항 시간에 풀고 싶어 한다.

최장 경로 문제는 주어진 그래프에서 길이가 최대인 단순 경로를 찾는 문제이다. 경로에 중복된 정점이 없으면 그 경로를 단순하다고 한다. 경로의 길이는 경로에 포함된 간선의 개수이다.

테스트 케이스가 여러 개 있다. 입력의 첫 줄에는 테스트 케이스의 수 $T$(약 $350$)가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 정점의 개수 $n$과 간선의 개수 $m$이 주어진다 ($3 \le n \le 10^4$, $n \le m \le n + 4$).

이어지는 $m$개의 줄에는 정점 $a_i$와 $b_i$를 잇는 간선이 하나씩 주어진다 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$).

그래프는 연결되어 있고 다중 간선이 없다고 보장된다.

입력의 총 크기는 4 MiB 이하이다.

각 테스트 케이스에 대해 최장 경로의 길이를 출력한다.