Isomorphic Suffix Trees
In this problem, your task is to find the number of distinct binary strings, composed of the characters '0' and '1', whose suffix trees are isomorphic to a given rooted tree (T).
Two rooted trees are considered isomorphic if they have the same number of vertices, (n), and there exists a way to label the vertices of each tree with unique integers from (1) to (n) such that:
The roots of both trees share the same label.
An edge exists between vertices labeled (a) and (b) in the first tree if and only if an edge exists between vertices labeled (a) and (b) in the second tree.
The suffix tree of a string (s) is a rooted tree that meets the following criteria:
Each edge is labeled with a non-empty string of '0's and '1's.
Each suffix of the string (s+''}\), except for the suffix "\(\textbf{)", corresponds to exactly one leaf (a vertex of degree 1 that is not the root). The concatenation of the edge labels along the path from the root to this leaf matches the suffix.
Any vertex that is neither a leaf nor the root must have a degree greater than two.
The tree has the smallest possible total length of edge labels among all trees satisfying properties 1-3.
For example, the suffix tree for the string "1100" is depicted as follows:
Your task is to determine the number of different binary strings whose suffix trees are isomorphic to the given tree (T).
Input
The first line contains an integer (n) ((2 n 25)) — the number of vertices in the tree. The vertices are numbered from (1) to (n), with the root being vertex (1). The next (n-1) lines describe the edges of the tree. Each line contains two integers (x_i) and (y_i) ((1 x_i, y_i n, x_i y_i)) — the vertices connected by the current edge.
Output
The first line should contain an integer (c) — the number of strings whose suffix tree is isomorphic to the tree described in the input (it is guaranteed that at least one such string exists). In the following (c) lines, list all the required strings in lexicographical order.