给你一棵有根树,由 $$$n$$$ 个顶点组成。顶点编号从$$$1$$$到$$$n$$$,根是顶点$$$1$$$。
您最多可以执行以下操作 $$$k$$$ 次:
- 选择树的边 $$$(v, u)$$$,使得 $$$v$$$ 是 $$$u$$$ 的父级;
- 删除边 $$$(v, u)$$$;
- 添加一条边 $$$(1, u)$$$ (即,使 $$$u$$$ 及其子树成为根的子树)。
树的高度是其顶点的最大深度,顶点的深度是从根到它的路径上的边数。例如,顶点 $$$1$$$ 的深度为 $$$0$$$,因为它是根,并且其所有子节点的深度为 $$$1$$$。
树的最小高度是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le n - 1$$$) - 树中的顶点数和可以执行的最大操作数。
第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i < i$$$) — 第 $$$i$$$ 个顶点的父顶点。顶点 $$$1$$$ 是根。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 通过执行最多 $$$k$$$ 操作可以获得的树的最小高度。
示例
输入 #1
5 5 1 1 1 2 2 5 2 1 1 2 2 6 0 1 2 3 4 5 6 1 1 2 3 4 5 4 3 1 1 1
输出 #1
2 1 5 3 1