전기 네트워크

대형 차량 충돌기(LHC, Large veHicle Collider)는 두 차량을 매우 큰 운동 에너지로 충돌시키기 위한, 세계에서 가장 크고 에너지가 높은 차량 가속 시설이다. 충돌 순간 차량 구조가 어떻게 견디는지 연구해 차량 안전 모형의 빠진 고리를 채우고, 비상 상황에서 차량의 각 부품이 어떻게 상호작용하는지 밝히는 것이 목적이다.

LHC에서 쓰는 차량은 전기 모터로 움직이며 실험에는 막대한 전력이 필요하다. 그래서 모든 시설은 전선 네트워크로 연결되어 있다. 전선 중 어느 하나가 고장 나더라도 임의의 두 시설이 (직접 또는 다른 시설을 거쳐) 여전히 연결되어 있으면, 그 네트워크를 이중 연결(doubly linked)되었다고 한다.

LHC는 불필요한 전선을 하나도 추가하지 않으면서, 네트워크를 이중 연결로 만들기 위해 최소한의 새 전선만 설치하려고 한다. 모든 시설이 이미 전선으로 연결되어 있는 네트워크가 주어질 때, 그 네트워크를 이중 연결로 만드는 데 필요한 새 전선의 최소 개수를 구하라.

그림 (a)

그림 (b)

그림 (c)

그림 (a)는 이중 연결된 네트워크이다. 그림 (b)는 두 차량 사이의 전선 하나를 제거하면 네트워크가 끊어지므로 이중 연결이 아니다. 그림 (c)처럼 전선 하나를 더 설치하면 이중 연결이 된다.

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트 케이스의 첫 줄에는 시설의 수 $N$과 이미 설치된 전선의 수 $M$이 주어진다 ($1 \le N \le 1000$, $1 \le M \le 100{,}000$). 이어지는 $M$개의 줄에는 각각 두 정수 $a$와 $b$ ($0 \le a, b \le N-1$)가 주어지며, 이는 시설 $a$와 $b$가 전선으로 직접 연결되어 있음을 뜻한다.

입력에서 같은 두 시설을 잇는 전선이 중복해서 주어지는 경우는 없다. 다만 두 시설 사이에 전선을 둘 이상 설치하는 것 자체가 금지된 것은 아니다.

각 테스트 케이스마다, 네트워크를 이중 연결로 만드는 데 필요한 새 전선의 최소 개수를 한 줄에 출력한다.