Семисегментний індикатор#6945
Семисегментний індикатор широко застосовується для відображення цифр завдяки використанню семи засвічуваних сегментів.
Нижче наведено ілюстрацію всіх сегментів, які використовуються у типовому семисегментному індикаторі (надалі для зручності використовуємо абревіатуру 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 > 0) отримують, якщо кожне ребро базового (ступеня ) графа розділити на k+1 частин і між ними вставити додаткових вершин.
Для ілюстрації нижче наведені SSD-графи ступеня для всіх цифр. Темні вершини — це додані вершини.
Вам надано граф із вершинами і ребрами. Потрібно знайти та вивести всі пари (ступінь, цифра), для яких цей граф може відповідати відповідним SSD-графам.
Перший рядок містить ціле число (1 \leq T \leq 20) — кількість тестових випадків. Далі слідують випадків. Кожен випадок починається з двох чисел (1 \leq n \leq 500) і (1 \leq m \leq 1000) — кількість вершин і кількість ребер. Далі у рядках наведено по парі чисел (, ), які означають наявність ребра між вершинами та . Вершини пронумеровані від до . Гарантується, що петель і повторюваних ребер у тестах немає.
Для кожного тесту виведіть одну відповідь. Перший рядок повинен мати формат Case X: Y (де — номер тесту, а — кількість пар (цифра, ступінь)). Далі — кожну пару (цифра, ступінь) у окремому рядку. Пари впорядковуються спочатку за цифрою, потім за ступенем. Між відповідями для різних тестів виводьте порожній рядок.
Приклад 1