체리 메시

당신의 친구는 최근 요리 수업을 마쳤고, 이제 멋진 디저트를 만들어 학교 친구들 앞에서 자랑하고 싶어 한다. 그는 Cherries Mesh라는 놀라운 디저트를 생각해 냈다. 이 요리를 만들기 위해 그는 이미 1부터 N까지 번호가 매겨진 체리를 모았다. 또한 서로 다른 체리의 순서 없는 각 쌍을 설탕으로 만든 달콤한 가닥으로 연결하기로 했다. 달콤한 가닥은 그 안의 설탕 함량에 따라 빨간색이거나 검은색이다. 검은색 가닥에는 한 단위의 설탕이 들어 있고, 빨간색 가닥에는 두 단위의 설탕이 들어 있다.

하지만 알고 보니 이제 디저트가 너무 달고, 요즘 그의 학교 친구들은 다이어트 중이라 보통 설탕이 적은 요리를 좋아한다. 그는 이제 몹시 혼란스러워하며 당신에게 도움을 청한다. 체리의 각 쌍이 설탕 가닥을 통해 직접 또는 간접적으로 연결되면서 요리의 설탕 함량이 가능한 한 최소가 되도록 제거해야 하는 모든 달콤한 가닥을 찾도록 도와줄 수 있는가?

제한

시간 제한: 테스트 세트당 15초. 메모리 제한: 1GB. 1 ≤ T ≤ 100 M ≤ N*(N-1)/2 모든 i에 대해, 1 ≤ $C_{i}$ ≤ N. 모든 i에 대해, 1 ≤ $D_{i}$ ≤ N. 모든 i에 대해, $C_{i}$ ≠ $D_{i}$. 모든 {$C_{i}$, $D_{i}$}는 서로 다르다.

테스트 세트 1 (공개)

1 ≤ N ≤ 100. 0 ≤ M ≤ 100.

테스트 세트 2 (비공개)

테스트 케이스 중 적어도 90%에 대해: 1 ≤ N ≤ 1000. 0 ≤ M ≤ 1000.

모든 테스트 케이스에 대해: 1 ≤ N ≤ $10^{5}$. 0 ≤ M ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 각각 체리의 수와 검은색 달콤한 가닥의 수를 나타내는 두 정수 N과 M이 포함된 줄로 시작한다.

그다음 M개의 줄이 주어지며, 각 줄은 검은색 가닥으로 연결된 체리 한 쌍을 설명한다. i번째 줄에는 번호가 $C_{i}$와 $D_{i}$인 체리가 주어지며, 이는 $C_{i}$ 체리와 $D_{i}$ 체리가 검은색 설탕 가닥으로 연결되어 있음을 나타낸다.

참고: 입력에 나타나지 않은 다른 모든 체리 쌍은 빨간색 가닥으로 연결되어 있다는 뜻이다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 가능한 최소 설탕 함량이다.

첫 번째 예제 케이스에는 체리가 두 개 있으며 검은색 가닥으로 연결되어 있다. 이 가닥을 제거하면 체리들의 연결이 끊어진다. 따라서 최소 설탕 함량은 1이다.

두 번째 예제 케이스에서는 번호가 2인 체리와 번호가 3인 체리 사이의 검은색 가닥을 유지하고 빨간색 가닥 중 아무 것이나 제거할 수 있으며, 그 결과 최소 설탕 함량은 3가 된다.