Two Centroids

Description:

Input:

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^{5}$$$) — the number of nodes of the final tree.

The second line of each test case contains $$$n - 1$$$ integers $$$p_1, p_2, \ldots, p_{n - 1}$$$ ($$$1 \le p_i \le i$$$) — the index of the vertex that is connected to vertex $$$i + 1$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^{5}$$$.

Output:

For each test case, output $$$n - 1$$$ integers. The $$$i$$$-th integer is the answer to the $$$i$$$-th query — the least number of operations required to make the current tree have two centroids.

We can show that an answer always exists.

Sample Input:

5
2
1
3
1 1
4
1 2 3
7
1 2 3 2 5 2
10
1 2 2 4 5 5 7 8 9

Sample Output:

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

Note:

The illustrations below are of the fourth example test case.

After the third query:

The tree already has vertices $$$2$$$ and $$$3$$$ as centroids, so no operations are needed.

After the fourth query:

Adding vertex $$$x$$$ to the tree makes vertices $$$2$$$ and $$$3$$$ centroids. Only one operation is needed.

After the fifth query:

Adding vertex $$$x$$$ and $$$y$$$ to the tree makes vertices $$$5$$$ and $$$2$$$ centroids. Two operations are needed.

After the sixth query:

Adding vertex $$$x$$$, $$$y$$$, and $$$z$$$ to the tree makes vertices $$$5$$$ and $$$2$$$ centroids. Three operations are needed.