Tree Isomorphism Classification

A tree is a connected undirected graph with \(N\) nodes and \(N-1\) edges. If a node is chosen as the root, then the tree becomes a rooted tree because every other node will have a unique predecessor. Two trees \(T_1\) and \(T_2\) are said to be isomorphic if we can relabel the nodes of \(T_1\) such that it becomes identical to \(T_2\) in structure. In other words, they share the same shape.

You are given M unrooted trees. Your task is to group them into equivalence classes such that trees in the same class are isomorphic.

Note: Two trees with a different number of nodes are not isomorphic.

inputFormat

The first line contains a single integer M, the number of trees.

Then, for each tree, the input is given as follows:

• The first line contains an integer N (the number of nodes in the tree).
• The next N-1 lines each contain two integers u and v representing an undirected edge between nodes u and v.

All nodes are numbered starting from 1.

outputFormat

First, output a single integer K representing the number of isomorphism classes.

Then output K lines, each describing one equivalence class. For each class, first output the number of trees in that class followed by the indices of the trees (1-indexed) in that class in increasing order. The order of the classes should be sorted by the smallest tree index in each class.

sample

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

3
2 1 2
1 3
1 4