题目描述

Consider a un-rooted tree $T$ which is not the biological significance of tree or plant, but a tree as an undirected graph in graph theory with $n$ nodes, labelled from 1 to $n$. If you cannot understand the concept of a tree here, please omit this problem.

Now we decide to colour its nodes with $k$ distinct colours, labelled from 1 to $k$. Then for each colour $i = 1, 2, \cdots, k$, define $E_i$ as the minimum subset of edges connecting all nodes coloured by $i$. If there is no node of the tree coloured by a specified colour $i$, $E_i$ will be empty.

Try to decide a colour scheme to maximize the size of $E_1 \cap E_2 \cap \cdots \cap E_k$, and output its size.

输入格式

The first line of input contains an integer $T$ ($1 \le T \le 1000$), indicating the total number of test cases.

For each case, the first line contains two positive integers $n$ which is the size of the tree and $k$ ($k \le 500$) which is the number of colours. Each of the following $n - 1$ lines contains two integers $x$ and $y$ describing an edge between them. We are sure that the given graph is a tree.

The summation of $n$ in input is smaller than or equal to $200000$.

输出格式

For each test case, output the maximum size of $E_1 \cap E_2 \cap \cdots \cap E_k$.

3
4 2
1 2
2 3
3 4
4 2
1 2
1 3
1 4
6 3
1 2
2 3
3 4
3 5
6 2

1
0
1