세븐 세그먼트 그래프

문제

세븐 세그먼트 디스플레이는 세그먼트 일곱 개를 켜고 꺼서 숫자 한 자리를 표시한다. 앞으로 세븐 세그먼트 디스플레이를 SSD로 줄여 쓴다.

일곱 세그먼트의 이름과 위치는 다음과 같다. 소수점을 나타내는 DP 세그먼트는 이 문제에서 쓰지 않는다.

 AAAA
F    B
F    B
 GGGG
E    C
E    C
 DDDD

세그먼트의 끝점은 모두 여섯 개다. 왼쪽 위, 오른쪽 위, 왼쪽 가운데, 오른쪽 가운데, 왼쪽 아래, 오른쪽 아래 끝점을 각각 LT, RT, LM, RM, LB, RB라고 하면 각 세그먼트가 잇는 두 끝점은 다음과 같다.

세그먼트	끝점
A	LT, RT
B	RT, RM
C	RM, RB
D	LB, RB
E	LM, LB
F	LT, LM
G	LM, RM

SSD가 $0$ 부터 $9$ 까지를 표시할 때 켜는 세그먼트는 다음과 같다.

$0$ : A, B, C, D, E, F
$1$ : B, C
$2$ : A, B, G, E, D
$3$ : A, B, C, D, G
$4$ : B, C, F, G
$5$ : A, C, D, F, G
$6$ : A, C, D, E, F, G
$7$ : A, B, C
$8$ : A, B, C, D, E, F, G
$9$ : A, B, C, D, F, G

숫자 한 자리의 표시는 그래프로 생각할 수 있다. 켜진 세그먼트의 끝점을 노드로, 켜진 세그먼트 자체를 간선으로 두면 그래프가 하나 나온다. 꺼진 세그먼트의 끝점은 노드에 넣지 않는다. 이렇게 얻은 그래프를 차수가 $0$ 인 SSD 그래프라고 한다.

차수가 $k$ ( $k > 0$ )인 SSD 그래프는 차수가 $0$ 인 SSD 그래프의 각 간선을 $k+1$ 개의 간선으로 나누고 그 사이에 노드 $k$ 개를 새로 넣어서 만든다. 예를 들어 차수가 $1$ 인 SSD 그래프에서는 원래 간선 하나가 간선 두 개와 그 사이의 새 노드 하나로 바뀐다.

노드 $n$ 개와 간선 $m$ 개로 이루어진 그래프가 주어진다. 주어진 그래프와 모양이 같은, 즉 그래프로서 동형인 SSD 그래프를 모두 찾아 그 숫자와 차수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 $T$ ( $1 \le T \le 20$ )가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 $n$ ( $1 \le n \le 500$ )과 간선의 개수 $m$ ( $1 \le m \le 1000$ )이 주어진다. 다음 $m$ 개 줄에는 간선이 잇는 두 노드의 번호 $u$ 와 $v$ 가 주어진다. 노드는 $1$ 번부터 $n$ 번까지 번호가 매겨져 있다. 같은 간선이 두 번 주어지는 경우와 $u$ 와 $v$ 가 같은 간선은 입력으로 주어지지 않는다.

출력

각 테스트 케이스마다 첫째 줄에 Case X: Y를 출력한다. $X$ 는 테스트 케이스의 번호이고, $Y$ 는 가능한 (숫자, 차수) 쌍의 개수다. 이어지는 $Y$ 개 줄에는 가능한 숫자와 차수를 한 줄에 하나씩 공백으로 구분해 출력한다. 숫자가 작은 순서대로 출력하고, 숫자가 같으면 차수가 작은 순서대로 출력한다. 테스트 케이스 사이에는 빈 줄을 하나 출력한다.