Семисегментный дисплей
Семисегментные цифровые дисплеи широко используются для отображения чисел, используя семь сегментов.
Ниже представлена схема, показывающая все сегменты, используемые в типичном семисегментном дисплее (далее будем использовать аббревиатуру SSD).
Рисунок 1: Сегменты, используемые для представления SSD.
Здесь DP обозначает десятичную точку, которая не требуется в контексте этой задачи.
Ниже представлены числа от 0 до 9, отображенные в SSD.
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
Представьте себе, что изображение цифры в SSD можно рассматривать как граф. Концы сегментов являются узлами, а сами сегменты — ребрами. Таким образом, цифры будут выглядеть следующим образом:
Мы называем это представление графом SSD нулевой степени. Граф SSD степени k (k > 0) создается путем деления каждого ребра графа нулевой степени на k+1 ребер и добавления k узлов между ними.
Для пояснения ниже показаны графы первой степени всех цифр. Более темные узлы — это вновь добавленные узлы.
Вам будет дан граф с n узлами и m ребрами. Ваша задача — вывести все пары (степень, цифра), для которых данный граф является допустимым.
Входные данные
Первая строка ввода содержит целое число T (1 ≤ T ≤ 20), обозначающее количество тестов. Далее следуют T наборов данных. Каждый набор начинается с пары чисел n (1 ≤ n ≤ 500) и m (1 ≤ m ≤ 1000) — количество узлов и количество ребер соответственно. Каждая из следующих m строк содержит пару чисел (u, v), указывающую на наличие ребра от узла u к узлу v. Узлы пронумерованы от 1 до n. Гарантируется, что во входных данных нет дубликатов или самопересекающихся ребер.
Выходные данные
Для каждого набора входных данных выведите один набор выходных данных. Первая строка набора должна быть в формате Case X: Y (где X — это порядковый номер входных данных, а Y — количество пар (цифра, степень)). Затем выведите каждую пару (цифра, степень) — по одной паре в строке. Пары должны быть отсортированы сначала по цифре, затем по степени. Между последовательными тестами выведите пустую строку.