Ізоморфні суфіксні дерева
У цій задачі вам потрібно визначити кількість різних рядків, що складаються з символів '0' та '1', суфіксні дерева яких ізоморфні заданому кореневому дереву T.
Два кореневих дерева вважаються ізоморфними, якщо вони мають однакову кількість вершин n і існує спосіб пронумерувати вершини кожного з них різними цілими числами від 1 до n так, що:
корені обох дерев мають однакові номери;
перше дерево містить ребро між вершинами з номерами a і b тоді і тільки тоді, коли друге дерево також містить ребро між вершинами з номерами a і b.
Суфіксне дерево рядка s — це кореневе дерево, яке задовольняє наступним умовам:
Кожному ребру дерева відповідає непорожній рядок, що складається з символів '0' та '1'.
Кожному суфіксу рядка s+''}, окрім суфікса "\textbf{", відповідає рівно один лист (тобто вершина степеня 1, що не є коренем), такий, що конкатенація рядків ребер на шляху від кореня до цього листа дорівнює даному суфіксу.
Степінь будь-якої вершини, що не є ні листом, ні коренем дерева, строго більший за два.
Дерево має мінімальну можливу сумарну довжину рядків, записаних на ребрах, серед усіх дерев, що задовольняють властивостям 1-3.
Наприклад, суфіксне дерево для рядка "1100" виглядає наступним чином:
Ваше завдання — за заданим кореневим деревом T визначити кількість різних рядків, що складаються з символів '0' та '1', суфіксні дерева яких ізоморфні T.
Вхідні дані
Перший рядок містить ціле число n (2 ≤ n ≤ 25) — кількість вершин дерева. Вершини дерева пронумеровані цілими числами від 1 до n. Коренем дерева є вершина з номером 1. У наступних n-1 рядках описуються ребра дерева. Кожен з цих рядків містить два цілі числа x_i і y_i (1 ≤ x_i, y_{i }≤ n, x_{i }≠ y_i) — номери вершин, які з'єднує чергове ребро дерева.
Вихідні дані
Перший рядок повинен містити ціле число c — кількість рядків, суфіксне дерево яких ізоморфне дереву, описаному у вхідних даних (гарантується, що хоча б один такий рядок існує). У наступних c рядках повинні бути виведені всі шукані рядки. Виводьте ці рядки в лексикографічному порядку.