Problem Description

You are given a tree with $n$ nodes, where the root is node $1$.

You can perform the following “Stand C operation” any number of times. In one “Stand C operation”:

Choose a leaf node $x$ in the tree, then choose an edge on the path from the root to $x$ and delete it; after that, add an edge connecting $x$ and the root.

You need to find the maximum possible diameter of the tree after performing some number of “Stand C operations”.

Note: A leaf node is defined as a node that is not the root and has degree $1$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

Then follow $T$ test cases. For each test case, the first line contains an integer $n$. The second line contains a sequence $f_i$ of length $n-1$, where the $i$-th value is the parent of node $i+1$ in the tree.

Output Format

For each test case, output one integer per line, the answer.

1
3
1 2

2

1
7
1 2 1 4 4 5

6

Hint

Explanation of Sample #1

If no operation is performed, the diameter of the tree is $2$. It can be proven that this is the maximum diameter.

Explanation of Sample #2

The tree in the sample is as follows:

Only one “Stand C operation” is needed: choose leaf node $6$, disconnect the edge from $1$ to $4$, then connect $6$ and $1$.

This will make the tree become a chain, with diameter $6$. It can be proven that this is the maximum diameter.

Constraints

Please pay attention to how constant factors affect program efficiency.

This problem enables subtask bundling and subtask dependencies.

For all testdata, $1\leq T\leq 10^4$, $2 \leq n \leq 2\times 10^5$, and the input is guaranteed to form a tree.

In particular, for Subtask 4, it is guaranteed that $\sum n\leq 3\times 10^6$.

Special property $A$: There does not exist a pair $(x,y)$ with $x\neq 1\land y\neq 1$ such that $\text{LCA}(x,y)=1$.

Translated by ChatGPT 5