Reset K Edges
Description
You are given a rooted tree, consisting of $n$ vertices. The vertices are numbered from $1$ to $n$, the root is the vertex $1$.
You can perform the following operation at most $k$ times:
- choose an edge $(v, u)$ of the tree such that $v$ is a parent of $u$;
- remove the edge $(v, u)$;
- add an edge $(1, u)$ (i. e. make $u$ with its subtree a child of the root).
The height of a tree is the maximum depth of its vertices, and the depth of a vertex is the number of edges on the path from the root to it. For example, the depth of vertex $1$ is $0$, since it's the root, and the depth of all its children is $1$.
What's the smallest height of the tree that can be achieved?
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.
The first line of each testcase contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$; $0 \le k \le n - 1$) — the number of vertices in the tree and the maximum number of operations you can perform.
The second line contains $n-1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$) — the parent of the $i$-th vertex. Vertex $1$ is the root.
The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.
For each testcase, print a single integer — the smallest height of the tree that can achieved by performing at most $k$ operations.
Input
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.
The first line of each testcase contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$; $0 \le k \le n - 1$) — the number of vertices in the tree and the maximum number of operations you can perform.
The second line contains $n-1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$) — the parent of the $i$-th vertex. Vertex $1$ is the root.
The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.
Output
For each testcase, print a single integer — the smallest height of the tree that can achieved by performing at most $k$ operations.
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
2
1
5
3
1