Substantial Isomorphism of Simplified Trees

An undirected tree is given. In the tree, a node whose degree is \(2\) is called a fake node, and all other nodes are called true nodes. The simplified tree of an undirected tree is defined as follows: its nodes are exactly the true nodes of the original tree, and two true nodes \(u\) and \(v\) are connected by an edge if and only if either they are adjacent in the original tree or there is a path connecting them in the original tree whose internal nodes are all fake nodes.

Two undirected trees are said to be substantially isomorphic if their respective simplified trees are isomorphic. That is, there exists a one-to-one correspondence between the nodes of the two simplified trees such that two nodes are adjacent in one tree if and only if their corresponding nodes are adjacent in the other tree.

Given several undirected trees, remove duplicates in the sense of substantial isomorphism (i.e. only retain one tree from every group of substantially isomorphic trees), and then output the number of remaining trees along with the number of nodes in each of their simplified trees sorted in ascending order.

Note

• The isomorphism between two trees is determined solely by the structure of their simplified trees.
• A node is considered a true node if its degree in the original tree is not equal to \(2\) (for example, leaves and nodes with degree at least \(3\) are true nodes; a single isolated node is also true).
• When contracting the tree to obtain its simplified tree, any maximal path whose internal nodes are all fake is replaced by a single edge connecting the endpoints (which are true nodes).

inputFormat

The input begins with an integer \(T\) (\(1 \le T\)), representing the number of trees. For each tree, the first line contains an integer \(n\) (\(1 \le n\)) indicating the number of nodes (nodes are numbered from \(1\) to \(n\)). Then \(n-1\) lines follow, each containing two integers \(u\) and \(v\) which represent an edge between nodes \(u\) and \(v\) in the tree.

outputFormat

First, output an integer \(k\), the number of trees remaining after removing trees that are substantially isomorphic to each other. Then, in the next line, output \(k\) integers separated by a space, where each integer is the number of nodes in the simplified tree of a remaining tree. The numbers must be sorted in ascending order.

sample

3
3
1 2
2 3
4
1 2
1 3
1 4
4
1 2
2 3
3 4

2
2 4