Problem Description

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.

Input Format

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 Format

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

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

1 
1 
3 
1 

Hint

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