Семисегментний дисплей
Сім сегментних цифрових дисплеїв є всюдисущими. Вони використовують сім сегментів для відображення чисел.
Ось зображення, яке показує всі сегменти, що використовуються в типовому семисегментному дисплеї (для зручності ми будемо використовувати абревіатуру 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 ступеня 0. Граф SSD ступеня k (k > 0) створюється шляхом поділу кожного ребра графа ступеня 0 на k+1 ребер і введення k вузлів між ними.
Для пояснення, графи ступеня 1 для всіх цифр показані нижче. Темніші вузли - це нові введені вузли.
Вам буде надано граф з 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 - це кількість пар (цифра, ступінь)) в одному рядку. Потім виведіть кожну пару (цифра, ступінь) - одну пару в кожному рядку. Пари повинні бути відсортовані спочатку за цифрою, потім за ступенем. Виведіть порожній рядок між послідовними тестовими випадками.