세븐 세그먼트 그래프

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

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

 AAAA
F    B
F    B
 GGGG
E    C
E    C
 DDDD

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

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$개 줄에는 가능한 숫자와 차수를 한 줄에 하나씩 공백으로 구분해 출력한다. 숫자가 작은 순서대로 출력하고, 숫자가 같으면 차수가 작은 순서대로 출력한다. 테스트 케이스 사이에는 빈 줄을 하나 출력한다.