Monkeys

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 153428/153428 K (Java/Others)

Description

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.

Input

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

Output

For each test case, print the minimum possible number of remaining edges.

Sample Input

2 4 4 1 2 3 4 3 1 1 1

Sample Output

2 2

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码