Seven-segment display#6945
A seven-segment display is widely used for displaying digits due to the use of seven illuminated segments.
Below is an illustration of all the segments used in a typical seven-segment display (hereinafter for convenience we use the abbreviation SSD).
Figure 1: Segments used in SSD.
Here DP denotes the decimal point, but it is not needed for this problem.
Below are the digits from 0 to 9, represented in SSD format.
0 uses segments 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
Now, imagine that the depiction of a digit on an SSD can be described as a graph. The ends of segments are nodes, while the segments themselves are edges. Thus, each digit has the following structure:
Such a construction is called an SSD graph of degree . An SSD graph of degree (k > 0) is obtained if each edge of the base (degree ) graph is divided into k+1 parts and additional nodes are inserted between them.
For illustration, below are SSD graphs of degree for all digits. Dark nodes are the added nodes.
You are given a graph with nodes and edges. You need to find and print all pairs (degree, digit) for which this graph can correspond to the respective SSD graphs.
The first line contains an integer (1 \leq T \leq 20) — the number of test cases. Then follow cases. Each case starts with two numbers (1 \leq n \leq 500) and (1 \leq m \leq 1000) — the number of nodes and the number of edges. Then in lines, each contains a pair of numbers (, ), meaning there is an edge between nodes and . Nodes are numbered from to . It is guaranteed that there are no loops or repeated edges in the tests.
For each test, output one answer. The first line should be in the format Case X: Y (where is the test number, and is the number of (digit, degree) pairs). Next, print each pair (digit, degree) on a separate line. Pairs are ordered first by digit, then by degree. Between the answers for different tests, print an empty line.
Example 1