There is a tree having N vertices. In the tree there are K monkeys (K <= N). A vertex can be occupied by at most one monkey. They want to remove some edges and leave minimum edges, but each monkey must be connected to at least one other monkey through the remaining edges.

Print the minimum possible number of remaining edges.

Print the minimum possible number of remaining edges.

The first line contains an integer T (1 <= T <= 100), the number of test cases.

Each test case begins with a line containing two integers N and K (2 <= K <= N <= 100000). The second line contains N-1 space-separated integers $a_1, a_2, …, a_{N-1}$, it means that there is an edge between vertex $a_i$ and vertex i+1 (1 <= $a_i$ <= i).

Each test case begins with a line containing two integers N and K (2 <= K <= N <= 100000). The second line contains N-1 space-separated integers $a_1, a_2, …, a_{N-1}$, it means that there is an edge between vertex $a_i$ and vertex i+1 (1 <= $a_i$ <= i).

提交代码