P17076 [ICPC 2017 Shenyang R] Tree

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