P6084 [JSOI2015] isomorphism

In an undirected tree, a node with degree $2$ is called a dummy node, and all other nodes are called real nodes. The simplified tree of an undirected tree is a tree whose nodes consist of all real nodes in the original tree. There is an edge between two real nodes in the simplified tree if and only if they are adjacent in the original tree, or there is a path connecting them in the original tree such that all intermediate nodes on the path are dummy nodes. If the simplified trees of two undirected trees are isomorphic (that is, there exists a one-to-one correspondence between their nodes such that for any two nodes in one tree, there is an edge between them if and only if there is an edge between their corresponding nodes in the other tree), then the two original undirected trees are called essentially isomorphic. Given several undirected trees, for each group of pairwise essentially isomorphic trees, keep only one and delete the rest. Count how many trees remain that are pairwise not essentially isomorphic, and output the numbers of nodes in their simplified trees in increasing order.

The first line contains a single positive integer $m$. Then $m$ undirected trees follow. For each tree, the first line contains the number of nodes $n$. The nodes are labeled from $1$ to $n$. Then $n-1$ lines follow, describing the $n-1$ undirected edges. Each line contains two distinct positive integers between $1$ and $n$, separated by a space, indicating that there is an undirected edge between these two nodes. There is no blank line between two trees.

The first line outputs one positive integer, the number of undirected trees in the input after removing those that are essentially isomorphic, denoted by $m_0\ (1\leq m_0\leq m)$. The second line contains $m_0$ positive integers in non-decreasing order, representing the numbers of nodes in the simplified trees of these $m_0$ undirected trees. Adjacent numbers are separated by a space.

#### Constraints For $100\%$ of the testdata, $2\leq m\leq 20, 2\leq n\leq 10^4$. Translated by ChatGPT 5