Ізоморфні суфіксні дерева#5941
У цій задачі вам потрібно визначити кількість різних рядків, що складаються з символів '0' та '1', суфіксні дерева яких ізоморфні заданому кореневому дереву T.
Два кореневих дерева вважаються ізоморфними, якщо вони мають однакову кількість вершин і існує спосіб пронумерувати вершини кожного з них різними цілими числами від до так, що:
корені обох дерев мають однакові номери;
перше дерево містить ребро між вершинами з номерами і тоді і тільки тоді, коли друге дерево також містить ребро між вершинами з номерами і .
Суфіксне дерево рядка — це кореневе дерево, яке задовольняє наступним умовам:
Кожному ребру дерева відповідає непорожній рядок, що складається з символів '0' та '1'.
Кожному суфіксу рядка +'$', окрім суфікса "$", відповідає рівно один лист (тобто вершина степеня , що не є коренем), такий, що конкатенація рядків ребер на шляху від кореня до цього листа дорівнює даному суфіксу.
Степінь будь-якої вершини, що не є ні листом, ні коренем дерева, строго більший за два.
Дерево має мінімальну можливу сумарну довжину рядків, записаних на ребрах, серед усіх дерев, що задовольняють властивостям -.
Наприклад, суфіксне дерево для рядка "1100" виглядає наступним чином:
Ваше завдання — за заданим кореневим деревом T визначити кількість різних рядків, що складаються з символів '0' та '1', суфіксні дерева яких ізоморфні T.
Перший рядок містить ціле число (2 \le n \le 25) — кількість вершин дерева. Вершини дерева пронумеровані цілими числами від до . Коренем дерева є вершина з номером . У наступних n-1 рядках описуються ребра дерева. Кожен з цих рядків містить два цілі числа x_i і y_i (1 \le x_i, y_i \le n, x_i \ne y_i) — номери вершин, які з'єднує чергове ребро дерева.
Перший рядок повинен містити ціле число — кількість рядків, суфіксне дерево яких ізоморфне дереву, описаному у вхідних даних (гарантується, що хоча б один такий рядок існує). У наступних рядках повинні бути виведені всі шукані рядки. Виводьте ці рядки в лексикографічному порядку.
Приклад 1