벌집들

벌은 가장 부지런한 곤충 중 하나입니다. 꽃에서 꿀과 꽃가루를 모으기 위해 벌들은 숲속의 나무에 의지합니다. 작업을 단순하게 하려고 벌들은 $n$개의 나무에 $0$부터 $n-1$까지 번호를 붙였습니다. 숲 전체를 돌아다니는 대신, 벌들은 정해진 경로 목록만 이용합니다. 하나의 경로는 두 나무를 잇고, 벌들은 그 경로를 양방향(한 나무에서 다른 나무로 직선으로) 이동할 수 있습니다. 목록에 없는 경로는 이용하지 않습니다.

기술이 발전하면서 벌들은 일하는 방식도 바꾸었습니다. 숲의 모든 나무를 맴도는 대신, 꽃이 많은 특정 나무들만 목표로 삼기로 했습니다. 그래서 목표로 한 몇몇 나무에 새로운 벌집을 짓기로 계획했습니다. 벌집이 모두 지어지면 벌집이 있는 나무에서만 식량을 모으고, 벌집이 없는 나무에는 가지 않도록 일부 경로를 목록에서 지웁니다. 즉, 벌집을 지은 나무들 사이를 잇는 경로만 남깁니다.

이제 벌들은 벌집을 지으려 합니다. 이 벌집들은, 여러 경로 중 어느 하나가 끊기더라도(그 경로에서 새나 동물이 벌을 방해할 수 있습니다) 남은 다른 경로들만으로 모든 벌집 사이를 오갈 수 있어야 합니다.

벌집 하나를 짓는 데 많은 노력이 들기 때문에, 벌들은 적어도 두 그루 이상의 나무에 벌집을 두되 그 개수를 가능한 한 적게 하려고 합니다. 주어진 나무와 경로를 이용해, 새로운 벌집 군집을 제안해 봅시다.

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($T \le 50$)가 주어집니다.

각 케이스는 빈 줄 하나로 시작합니다. 그다음 줄에 두 정수 $n$ ($2 \le n \le 500$)과 $m$ ($0 \le m \le 20000$)이 주어지며, $n$은 나무의 수, $m$은 경로의 수입니다. 이어지는 $m$개의 줄에는 각각 두 정수 $u$와 $v$ ($0 \le u, v < n$, $u \ne v$)가 주어지며, 나무 $u$와 나무 $v$를 잇는 하나의 경로를 뜻합니다. 같은 두 나무를 잇는 경로는 최대 하나이며, 같은 경로가 입력에 두 번 주어지지는 않습니다.

각 케이스에 대해, Case X: (X는 케이스 번호) 뒤에 제안된 벌집 군집의 벌집 개수를 출력합니다. 그러한 군집을 만들 수 없다면 개수 대신 impossible을 출력합니다.

입력 데이터가 큽니다. 빠른 입출력을 사용하세요.