체리 메시

친구가 최근 요리 수업을 마치고 학교 친구들 앞에서 멋진 디저트를 자랑하고 싶어 한다. 친구는 체리 메시(Cherries Mesh)라는 디저트를 생각해 냈다. 디저트를 만들기 위해 1번부터 N번까지 번호가 붙은 체리를 이미 모아 두었다. 그리고 서로 다른 체리 두 개를 짝지어 각각을 설탕으로 만든 달콤한 가닥으로 연결하기로 했다. 가닥은 설탕 함량에 따라 빨간색 또는 검은색이다. 검은색 가닥 하나에는 설탕이 1단위, 빨간색 가닥 하나에는 설탕이 2단위 들어 있다.

그런데 디저트가 너무 달아졌다. 요즘 학교 친구들은 다이어트 중이라 설탕이 적은 디저트를 좋아한다. 친구는 어떻게 해야 할지 몰라 도움을 청한다. 모든 체리 쌍이 설탕 가닥으로 직접 또는 간접적으로 연결되면서 설탕 함량이 최소가 되도록, 어떤 가닥을 제거해야 하는지 구해 줄 수 있는가?

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 체리의 수 N과 검은색 가닥의 수 M이 주어진다.

이어서 M개의 줄이 주어지며, 각 줄은 검은색 가닥으로 연결된 체리 두 개를 나타낸다. i번째 줄에는 체리 번호 Ci와 Di가 주어지며, 이는 Ci번 체리와 Di번 체리가 검은색 설탕 가닥으로 연결되어 있음을 뜻한다.

참고: 입력에 없는 나머지 체리 쌍은 모두 빨간색 가닥으로 연결되어 있다.

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

• 1 ≤ T ≤ 100
• M ≤ N*(N-1)/2
• 1 ≤ Ci ≤ N, 모든 i에 대해
• 1 ≤ Di ≤ N, 모든 i에 대해
• Ci ≠ Di, 모든 i에 대해
• 모든 {Ci, Di}는 서로 다르다.

첫 번째 예시에서 체리는 두 개이고 검은색 가닥으로 연결되어 있다. 어느 가닥을 제거해도 체리가 분리되므로 최소 설탕 함량은 1이다.

두 번째 예시에서는 2번 체리와 3번 체리 사이의 검은색 가닥을 남기고 빨간색 가닥을 제거하면 최소 설탕 함량 3이 된다.