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?


-----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.


-----Examples-----

Input
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
Output
2
1
5
3
1


-----Note-----

None

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Sorting

Greedy algorithms

Tree algorithms

Data structures


Solutions:
def check(pars, dep, k):
	_oper = 0
	depths = [1 for i in range(len(pars))]
	for i in range(len(pars) - 1, 0, -1):
		if depths[i] == dep and pars[i] != 0:
			_oper += 1
		else:
			par = pars[i]
			depths[par] = max(depths[par], depths[i] + 1)
	return _oper <= k
t = int(input())
for _ in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	pars = [0]
	pars_temp = input().split()
	pars += [int(i) - 1 for i in pars_temp]
	(low, high) = (1, n - 1)
	while low < high:
		mid = (low + high) // 2
		if check(pars, mid, k):
			high = mid - 1
		else:
			low = mid + 1
	if high >= 1 and check(pars, high, k):
		print(high)
	else:
		print(high + 1)


for _ in range(int(input())):
	(q, k) = map(int, input().split())
	arr = [-1, 0] + [int(i) for i in input().split()]
	(l, r) = (1, q - 1)
	while l < r:
		mid = (l + r) // 2
		tot = 0
		h = [0] * (q + 1)
		for i in range(q, 1, -1):
			if h[i] == mid - 1 and arr[i] != 1:
				tot += 1
			else:
				h[arr[i]] = max(h[arr[i]], h[i] + 1)
		if tot <= k:
			r = mid
		else:
			l = mid + 1
	print(l)


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	P = list(map(int, input().split()))
	child = [[] for _ in range(n + 1)]
	par = [-1] * (n + 1)
	for i in range(1, n):
		child[P[i - 1]].append(i + 1)
		par[i + 1] = P[i - 1]
	stack = [(0, 1)]
	depth = [0] * (n + 1)
	while stack:
		(d, node) = stack.pop()
		depth[node] = d
		for ch in child[node]:
			stack.append((d + 1, ch))
	D = sorted([(v, i + 1) for (i, v) in enumerate(depth[1:])])
	(lo, hi) = (1, n - 1)
	while lo < hi:
		mid = (lo + hi) // 2
		cnt = 0
		vis = set()
		i = n - 1
		while i >= 0 and cnt <= k:
			(d, idx) = D[i]
			if d <= mid or idx in vis:
				i -= 1
				continue
			curr = 0
			while idx > 0 and curr < mid - 1:
				idx = par[idx]
				curr += 1
			stack = [idx]
			vis.add(idx)
			while stack:
				node = stack.pop()
				for ch in child[node]:
					if ch not in vis:
						vis.add(ch)
						stack.append(ch)
			cnt += 1
			i -= 1
		if cnt <= k:
			hi = mid
		else:
			lo = mid + 1
	return hi
for _ in range(int(input())):
	print(solve())