树是没有环的连通图。有根树有一个特殊的顶点,称为根。顶点 $$$v$$$ 的父顶点(与根不同)是从根到顶点 $$$v$$$ 的最短路径上 $$$v$$$ 顶点的前一个顶点。顶点 $$$v$$$ 的子节点都是以 $$$v$$$ 为父节点的顶点。
给你一棵有 $$$n$$$ 个顶点的有根树。顶点 $$$1$$$ 是根。最初,所有顶点都是健康的。
每秒执行两个操作,即扩散操作,然后是注入操作:
1. 传播:对于每个顶点 $$$v$$$,如果 $$$v$$$ 中至少有一个孩子被感染,则您最多可以通过感染您选择的 $$$v$$$ 中的其他一个孩子来传播疾病。
2.注射:可以选择任意健康的顶点进行感染。
这个过程每秒重复一次,直到整棵树被感染。您需要找到感染整棵树所需的最少秒数。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) - 给定树中的顶点数。
每个测试用例的第二行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$),其中 $$$p_i$$$ 是树中第 $$$i$$$ 个顶点的祖先。
保证给定的图是一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,您应该输出一个整数 - 感染整个树所需的最少秒数。
示例
输入 #1
5 7 1 1 1 2 2 4 5 5 5 1 4 2 1 3 3 1 6 1 1 1 1 1
输出 #1
4 4 2 3 4
注意
该图像描绘了每秒第一个测试用例中的树。
如果顶点未受感染,则其为黑色。如果顶点在前一秒内被注射感染,则该顶点呈蓝色。如果顶点在前一秒内因传播而受到感染,则该顶点呈绿色。如果顶点早于前一秒被感染,则该顶点呈红色。
请注意,您可以选择通过传播和注入感染哪些顶点。