Изоморфные суффиксные деревья

В этой задаче необходимо по заданному корневому дереву T определить количество различных строк, состоящих из символов '0' и '1', суффиксные деревья которых изоморфны T.

Два корневых дерева называются изоморфными, если они состоят из одинакового количества вершин n и можно пронумеровать вершины каждого из них различными целыми числами от 1 до n так, что:

• корни обоих деревьев имеют одинаковые номера;

• первое дерево содержит ребро между вершинами с номерами a и b тогда и только тогда, когда второе дерево также содержит ребро между вершинами с номерами a и b.

В этой задаче суффиксное дерево строки s — это корневое дерево, удовлетворяющее следующим условиям:

1. Каждому ребру дерева поставлена в соответствие непустая строка, состоящая из символов '0' и '1'.

2. Каждому суффиксу строки s+''}, кроме суффикса "\textbf{", соответствует ровно один лист (то есть вершина степени 1, не совпадающая с корнем) такой, что конкатенация строк ребер на пути от корня к этому листу равна данному суффиксу.

3. Степень любой вершины, не являющейся ни листом, ни корнем дерева, строго больше двух.

4. Дерево имеет минимальную возможную суммарную длину строк, записанных на ребрах, среди всех деревьев, удовлетворяющих свойствам 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строках должны быть выведены все искомые строки. Выводите эти строки в лексикографическом порядке.

Примеры