상근이의 여행

상근이는 겨울방학을 맞아 $N$개국을 여행하며 자아를 찾기로 했다. 그런데 처음 타 보는 비행기를 무서워해서, 되도록 적은 종류의 비행기만 타고 나라 사이를 오가려고 한다.

이번 방학의 비행 스케줄이 주어질 때, 모든 나라를 여행하려면 비행기가 최소 몇 종류 필요한지 구하자.

한 나라에서 다른 나라로 갈 때 중간에 다른 나라를 거쳐도 되고, 이미 다녀온 나라를 다시 지나가도 된다.

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

각 테스트 케이스는 다음과 같이 주어진다.

• 첫째 줄에 나라의 수 $N$과 비행기 종류의 수 $M$이 주어진다. ($2 \le N \le 1000$, $1 \le M \le 10000$)
• 다음 $M$개 줄에 정수 $a$와 $b$가 주어진다. $a$와 $b$ 사이를 왕복하는 비행기가 있다는 뜻이다. ($1 \le a, b \le N$, $a \ne b$)

주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.

테스트 케이스마다 상근이가 모든 나라를 여행하려면 타야 하는 비행기 종류의 최소 개수를 한 줄에 출력한다.