좀비 사이의 인디아나 존스 2

앞선 문제 "좀비 사이의 인디아나 존스"에서 인디아나가 찾아낸 신체와 정신 지배의 부적은 고장 나 있었습니다. 만약 그 부적이 제대로 작동했다면 이야기는 어떻게 흘러갔을까요?

미로의 구조는 이전 문제와 같습니다.

• 미로에는 $1$번부터 $N$번까지 번호가 붙은 $N$개의 방이 있습니다. $1$번 방에는 인디아나가 있습니다. 나머지 방에는 각각 언데드(좀비)가 한 마리씩 있습니다. 방들은 양방향 통로로 연결되어 있습니다.
• 매 턴마다 살아 있는 모든 좀비는, 자신이 있는 방에서 인디아나가 있는 방까지의 최단 경로 위 다음 방으로 통로를 따라 한 칸 이동합니다. 자신의 방에서 인디아나의 방으로 갈 수 없다면 그 자리에 그대로 서 있습니다. 한 방에서 인디아나의 방으로 가는 최단 경로가 여러 개라면, 그 방의 좀비들은 입력에서 가장 먼저 등장한 통로를 선택합니다.

이번에는 인디아나가 제대로 작동하는 부적을 가지고 있습니다. 인디아나는 이 부적으로 좀비들이 (인디아나를 잡아먹을 권리를 두고) 서로 다투게 만들려고 합니다. 부적을 쓰면 인디아나는 맨 처음에 서로 겹치지 않는 좀비 쌍을 원하는 개수만큼 골라 각 쌍을 라이벌로 지정할 수 있습니다.

어떤 라이벌 쌍의 한 좀비가, 다음 턴에 같은 쌍의 다른 좀비가 들어올 방에 서 있게 되는 순간(즉 다른 좀비가 그 방으로 한 칸 이동하기 직전) 곧바로 싸움이 벌어집니다(다음 턴이 아니라 바로 그 순간에). 인디아나에게서 더 멀리 있는 좀비는 자신의 라이벌이 인디아나를 먼저 잡아먹을 위치에 있음을 깨닫고, 둘 사이의 통로를 통해 상대에게 달려듭니다. 둘은 머리를 부딪쳐 함께 죽습니다.

인디아나의 방에 도착한 좀비는 즉시 부적으로 머리를 얻어맞아 죽으며, 그 순간부터는 자신의 라이벌과 싸울 수 없습니다.

고른 모든 라이벌 쌍에서 위와 같은 싸움이 실제로 일어나도록 할 때, 인디아나가 고를 수 있는 서로 겹치지 않는 라이벌 쌍의 최대 개수를 구하세요.

첫째 줄에 테스트 집합의 개수를 나타내는 자연수 $Z$ ($Z = 1$)가 주어집니다. 이어지는 줄들에 각 테스트 집합이 차례로 주어집니다.

각 테스트 집합의 첫째 줄에는 공백으로 구분된 두 자연수 $N$과 $M$ ($1 \le N, M \le 10^6$)이 주어집니다. $N$은 미로의 방 개수, $M$은 통로의 개수입니다.

이어지는 $M$개의 줄에는 통로가 한 줄에 하나씩 주어집니다. 각 줄은 서로 다른 두 자연수 $A$와 $B$ ($1 \le A, B \le N$)로 이루어지며, 방 $A$와 방 $B$를 잇는 양방향 통로가 있음을 뜻합니다. 어떤 두 방도 최대 하나의 통로로만 연결됩니다.

각 테스트 집합마다, 싸움을 벌이도록 유도할 수 있는 라이벌 좀비 쌍의 최대 개수를 한 줄에 출력하세요.