Seven segment numeric displays are ubiquitous. It uses seven segments to display numbers. Here is a figure which depicts all the segments used in a typical seven segment display (We’ll be using the acronym SSD for convenience from now on). \includegraphics{https://static.e-olymp.com/content/df/df3f1564390e404c859b8c53e45fac16dc01d535.jpg} \textit{\textbf{Figure 1}}: Segments used for SSD representation. Here, DP represents decimal place which is not necessary in the context of this problem. And here are the numbers from \textbf{0} to \textbf{9} represented in SSD. \includegraphics{https://static.e-olymp.com/content/ae/ae6d7cbfd2ef604165f506c2a73dff783373cad8.jpg} \textbf{0} uses segments \textbf{A, B, C, D, E, F} \textbf{1: B, C} \textbf{2: A, B, G, E, D} \textbf{3: A, B, C, D, G} \textbf{4: B, C, F, G} \textbf{5: A, C, D, F, G} \textbf{6: A, C, D, E, F, G} \textbf{7: A, B, C} \textbf{8: A, B, C, D, E, F, G} \textbf{9: A, B, C, D, F, G} Now, imagine the SSD representation of a digit as a graph. The endpoints of the segments are the nodes and segments are edges. So, the digits will look like: \includegraphics{https://static.e-olymp.com/content/10/10ad026cd50834f2da6cd793e91f6a22ed6ee90a.jpg} We call this representation a \textbf{0}-degree SSD graph. A \textbf{k}-degree (\textbf{k} > \textbf{0}) SSD graph is made by dividing each edge of a \textbf{0}-degree graph into \textbf{k+1} edges and introducing \textbf{k} nodes in between them. To explain more, \textbf{1}-degree graphs of all digits are shown below. The darker nodes are the newly introduced nodes. \includegraphics{https://static.e-olymp.com/content/57/576d32485918ac310bcd8a65529aa7a9db5fdc7d.jpg} \includegraphics{https://static.e-olymp.com/content/f9/f9883106949d820f5fcf258509d47ae97e355d53.jpg} \includegraphics{https://static.e-olymp.com/content/ec/ecdfb819e9d008ac445ff0a143dc5b3e64f5df9a.jpg} You’ll be given a graph with \textbf{n} nodes and m edges. You’ll need to print all the (degree, digit) pairs for which the given graph is valid. \InputFile The first line of the input contains an integer which denotes the number of test cases \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{20}). \textbf{T} sets of case will follow. Each case will start with a couple of numbers \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{500}) and \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{1000}) - the number of nodes and the number of edges respectively. Each of the next \textbf{m} lines will contain a pair of numbers (\textbf{u}, \textbf{v}) meaning that there is an edge from node \textbf{u} to node \textbf{v}. Nodes are numbered from \textbf{1} to \textbf{n}. It’s guaranteed that there is no duplicate or self-edges in the input. \OutputFile For each set of inputs, output one set of output. First line of a set should be of the format, \textbf{Case X: Y} (here, \textbf{X} is the serial of the input and \textbf{Y} is the number of (digit, degree) pairs) in a line. Then print each (digit, degree) pair - one pair in each line. The pairs should be sorted according to digit first then degree. Each number in a pair should be separated with a space. Print a blank line between consecutive test cases.