#P7870. Tree Cutting

Tree Cutting

Tree Cutting

Problem Description

Given a tree (connected undirected graph with nn vertexes and n−1n - 1 edges), you are required to delete as few vertexes as possible such that the remaining graph is still a tree and its diameter shall not exceed kk. The diameter of a tree is the length of its longest path.

Input

The first line contains one positive integer TT (1≤T≤151\le T \le 15), denoting the number of test cases. For each test case: The first line of the input contains two integers n,k (1≤n,k≤300000)n, k\,(1\le n,k \le 300000). Each of the following n−1n - 1 lines contains two integers u,v (1≤u,v≤n,u≠v)u, v\, (1\le u,v \le n, u\neq v), indicating that there is an edge connecting vertex uu and vv in the tree.

Output

For each test case: You should just output one integer indicating the number of vertexes to be deleted.

Sample Input

1
10 3
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10

Sample Output

4

Source

2020 Multi-University Training Contest 10