Define a Uniform tree as one in which all of the nodes at a given level (i.e. distance from the root) have the same degree (i.e. number of children). Since all of the nodes at a given level have the same number of children, a uniform tree can be represented as simply a list of integers, indicating the number of children at each level. For example, the list [2 3 5 0] represents a tree where the root has $2$ children, each child of the root has $3$ children, each grandchild has $5$ children, and each great-grandchild has no children, and is therefore a leaf.
For the purposes of this problem, redefine Subtree as a connected subgraph of a tree that includes the tree’s root. This is a bit different than the typical definition of Subtree.
Given a description of a tree, find all of the unique Uniform Subtrees of that tree. For example, here is a tree and all of its unique uniform subtrees:
There will be a single test case in the input. Each test case will consist of a single tree, represented as a single string on one line. The string will be a sequence of matched opening and closing parentheses. Each matched pair represents a node, and the string between represents its children. There will not be more than $4\, 000$ nodes in the tree. There will be no whitespace, or any other characters, in the string.
Output every unique uniform subtree of the given tree as a list of integers, one subtree (and thus one list) per line. Print a single space between integers, and no spaces anywhere else. Do not print any blank lines between lists, or between test cases. Print the lists for a given test case sorted by the first element, then the second, then the third, and so on.
(Note: the first sample input & output case corresponds to the pictured tree and subtrees.)
|Sample Input 1||Sample Output 1|
0 1 0 1 1 0 1 1 1 0 1 1 2 0 1 2 0 1 3 0 2 0 2 1 0 2 1 1 0
|Sample Input 2||Sample Output 2|
0 1 0