[2018 SCPC 본선]

우주정거장2

이전에 우주 정거장을 설계했던 기억이 어렴풋이 있을 것이다.

우주정거장은 공 모양의 캡슐들과 각각 두개의 캡슐을 연결하는 통로들로 만들어진다.

우주정거장이 최종적으로 어떻게 구성될지는 이미 정해져 있다고 한다.

우주정거장을 우주에 올리는 방법은 두단계로 이루어진다.

1단계에서 우주 정거장의 최초구성을 지상에서 만들어 궤도에 올린다.

2단계에서는 아래의 작업이 여러 차례 반복된다. 



  ㆍ  작업: 이미 통로로 직접 연결된 두 캡슐 와 에 대해서 와 캡슐 를 통로로 연결하고 와 를 통로로 연결한다.

              여기서, 캡슐 와 두 통로는 우주정거장에 새로 추가되는 것이다.



이전에는 우주 정거장의 (캡슐의 개수가) 가장 작은 최초 구성(1단계 구성)에 캡슐이 몇 개가 있는지 계산해 보았었다. 

당신의 보스가 갑자기 마음이 변해 가능한 가장 작은 최초 구성이 모두 몇 가지가 있는지 알아보라고 명령하였다.

다음 그림이 최종 구성이라고 하자. 

 

위의 최종 구성에 대한 가능한 가장 작은 최초 구성은 아래 보인 4가지가 있음을 알 수 있다.

 



우주정거장의 최종구성을 입력으로 받아 가능한 가장 작은 최초구성의 개수를 찾는 프로그램을 작성하시오. 




입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 가 주어지고,

이후 차례로   개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 최종 구성의 캡슐 수 N과 통로 수 M이 정수로 어진다.

캡슐들은 1번부터 번까지 번호가 붙어 있다.

다음 개의 줄에 각 통로가 연결하는 캡슐 번호의 쌍이 하나씩 주어진다.

한 통로는 서로 다른 두 캡슐을 연결하며, 한 쌍의 캡슐을 연결하는 통로는 최대 1개이다.

임의의 캡슐에서 다른 임의의 캡슐로 1개 이상의 통로를 이용하여 이동하는 것이 가능함이 보장된다.




출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다.

이때 는 테스트 케이스의 번호이다.

그 다음 줄에 가능한 가장 작은 최초구성의 개수를 1,000,000,007로 나눈 나머지를 출력한다. 

입출력예

입력
3
3 3
1 2
3 1
2 3
4 4
1 2
2 3
3 4
1 4
5 6
1 2
2 3
1 4
2 4
2 5
3 5
출력
Case #1
3
Case #2
1
Case #3
4

돌아가기