Дерева покриття у безпечному шаблоні блокування
Блокування екрана на смартфоні може бути реалізовано за допомогою малюнка. Малюнок для розблокування має 9 вершин на сітці 3×3. У цій задачі ми змінимо розмір сітки, дозволивши йому змінюватися від 2×2 до m×m, і лише обмежена кількість з'єднань дозволена між парами сусідніх вершин. Назвемо такий модифікований сітковий граф G, де V - множина його вершин, а E - множина ребер (з'єднань). Приклади сіткових графів 2×2, 3×3 і 4×4 наведені на рисунках. Кутові вершини мають не більше 3 з'єднань, а центральні до 8 з'єднань. Дозволені з'єднання лише між сусідніми вершинами.
Остовне дерево визначається як набір ребер графа, що не утворюють цикл, і по яких можна пройти між будь-якими двома вершинами. Остовне дерево містить m^2 = n вершин і n - 1 ребро. Остовні дерева в графі можуть мати різні види і форми.
Для обчислення кількості остовних дерев у G, позначимо вершини G мітками v_1, ..., v_n. Утворимо матрицю n×n дерева T = [t_ij] наступним чином.
Якщо i = j, то t_ii дорівнює числу суміжних ребер з v_i в G.
Якщо i ≠ j, то t_ij = 0, якщо не існує ребра між v_i і v_j в G.
Якщо i ≠ j, то t_ij = -1, якщо існує ребро між v_i і v_j в G.
Тоді кількість остовних дерев у G дорівнює
cofactor of a_ij = (-1)^i+jM_ij
де M_ij - детермінант матриці (n-1)×(n-1) отриманої видаленням рядка i і стовпця j з матриці дерева T. Значення будь-якого алгебраїчного доповнення T дає один і той самий результат.
Приклад 1: Матриця дерева T для сіткового графа 2×2 дорівнює
Обчислимо алгебраїчне доповнення T. Наприклад, виключивши рядок 1 і стовпець 1, отримаємо
Тому кількість остовних дерев дорівнює 16.
Приклад 2: Матриця дерева T сіткового графа 3×3 має вигляд
Значення будь-якого алгебраїчного доповнення T одне і те ж і дорівнює кількості остовних дерев.
Підказка: Обчислити визначник можна використовуючи елементарні операції над рядками:
Слід перетворити початкову матрицю до верхньої трикутної (всі елементи нижче головної діагоналі дорівнюють нулю). Перетворіть матрицю рядок за рядком використовуючи елементарні операції на рядках, внаслідок чого всі елементи нижче головної діагоналі стануть нульовими. Потім перемножте елементи головної діагоналі і отримаєте значення визначника.
Напишіть програму, яка обчислить кількість остовних дерев для модифікованого сіткового графа розміру m×m.
Вхідні дані
Перша рядок містить кількість тестів n (1 ≤ n ≤ 5). Кожен тест містить одне ціле число m (2 ≤ m ≤ 6) - розмір m×m сітки - графа.
Вихідні дані
Для кожного тесту ваша програма повинна вивести кількість остовних дерев, що вказує на кількість варіантів остовних дерев для заданого модифікованого сіткового графа. Виведіть по одному рядку для кожного тесту відповідно.
Приклади
Примітка
У прикладі є лише один тест (n = 1). Для першого тесту при m = 2 є 16 різних остовних дерев. Усі вони перелічені нижче. Вашій програмі НЕ потрібно малювати всі зображення.
