Given a tree (connected undirected graph with n vertexes and n−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 k. The diameter of a tree is the length of its longest path.
输入格式
The first line contains one positive integer T (1≤T≤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).
Each of the following n−1 lines contains two integers u,v(1≤u,v≤n,u≠v), indicating that there is an edge connecting vertex u and v in the tree.
输出格式
For each test case:
You should just output one integer indicating the number of vertexes to be deleted.