P5043 [Template] Tree Isomorphism / [BJOI2015] Tree Isomorphism.

A tree is a very common data structure. We call a connected undirected graph with $N$ vertices and $N - 1$ edges a tree. If we choose a vertex as the root and traverse from the root, then every other vertex has a predecessor. This tree becomes a rooted tree. For two trees $T_1$ and $T_2$, if we can relabel all vertices of $T_1$ so that $T_1$ and $T_2$ become exactly the same, then these two trees are isomorphic. That is, they have the same shape. Now you are given $M$ unrooted trees. Please partition them into several equivalence classes according to the isomorphism relation.

The first line contains an integer $M$. The next $M$ lines each contain several integers describing one tree. The first integer is $N$, the number of vertices. Then follow $N$ integers, which in order give the parent vertex number of each vertex numbered from $1$ to $N$. The parent number of the root vertex is $0$.

Output $M$ lines. Each line contains one integer, representing the smallest index among the trees that are isomorphic to the corresponding tree.

Trees numbered $1$, $2$, and $4$ are isomorphic. The tree numbered $3$ is only isomorphic to itself. For $100\%$ of the testdata, it is guaranteed that $1 \leq N, M \leq 50$. Translated by ChatGPT 5