길의 사이클

부쿠레슈티 공과대학교 공원에는 $M$개의 길이 있고, 각 길은 공원의 $N$개 교차로($1$부터 $N$까지 번호가 매겨져 있음) 중 두 개를 잇는다. 어떤 두 교차로도 두 개 이상의 길로 연결되어 있지 않으며, 어느 교차로에서든 하나 이상의 길로 이루어진 경로를 따라 다른 모든 교차로로 갈 수 있다. 길로 이루어진 사이클이 지나는 모든 교차로를 정확히 한 번씩만 지날 때, 그 사이클을 단순 사이클이라고 한다.

대학 본부는 같은 대학 출신 수상자들의 사진이 하나의 단순 사이클을 이루는 길들 위에 놓이도록, 지역 대학생 프로그래밍 대회 수상자들의 사진을 길에 걸고 싶어 한다. 그래서 가장 성공적인 대학에는 가장 긴 단순 사이클을 배정하려고 하며, 결국 가장 긴 사이클을 찾는 것이 문제이다. 다행히 공원의 각 길은 많아야 하나의 단순 사이클에만 속한다(그림 참조).

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 양의 정수 $N$과 $M$이 있는 줄로 시작한다($4 \le N \le 4444$). 각각 교차로의 수와 길의 수이다. 이어지는 $M$개의 줄에는 하나의 길이 잇는 두 교차로의 번호가 주어진다.

각 테스트 케이스마다, 가장 긴 단순 사이클의 길이를 한 줄에 출력한다. 여기서 길이는 그 사이클에 포함된 길의 개수(즉, 교차로의 개수)이다.