Диграфи#6776
Диграф — це орієнтований граф... але не цього разу. Давайте на хвилинку відволічемося від складних термінів і поговоримо про мови (людські, а не PHP).
Диграф — це пара літер, що представляє одну фонему (звук). Наприклад, "ch" в англійській мові (як у слові "church") — це один приголосний звук. Мови Центральної Європи багаті на диграфи: угорське "sz", чеське "ch" і польське "rz" є яскравими прикладами.
Диграфи можуть бути досить дратівливими для тих, хто не звик їх використовувати. Тому ми створимо лист-загадку для таких людей. Вам потрібно скласти найбільший можливий квадрат рядків з малих літер англійського алфавіту, щоб жоден з його рядків або стовпців не містив жодного з заданих диграфів. Тобто, жодні дві послідовні літери (якщо читати зверху вниз або зліва направо) не повинні утворювати диграф.
Перша стрічка містить кількість тестів . Структура кожного тесту така:
Кожен тест починається з числа (0 \le n \le 676) заборонених диграфів. Наступні рядків містять ці диграфи.
Для кожного тесту виведіть квадрат максимально можливого розміру, який не містить диграфів. Якщо можливо побудувати квадрат розміром 20 \times 20 або більше, виведіть лише квадрат 20 \times 20.
Приклад 1