C. Tree Cutting
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ vertices.

Your task is to find the maximum number $$$x$$$ such that it is possible to remove exactly $$$k$$$ edges from this tree in such a way that the size of each remaining connected component$$$^{\dagger}$$$ is at least $$$x$$$.

$$$^{\dagger}$$$ Two vertices $$$v$$$ and $$$u$$$ are in the same connected component if there exists a sequence of numbers $$$t_1, t_2, \ldots, t_k$$$ of arbitrary length $$$k$$$, such that $$$t_1 = v$$$, $$$t_k = u$$$, and for each $$$i$$$ from $$$1$$$ to $$$k - 1$$$, vertices $$$t_i$$$ and $$$t_{i+1}$$$ are connected by an edge.

Input

Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of sets of input data. This is followed by a description of the sets of input data.

The first line of each set of input data contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k < n \le 10^5$$$) — the number of vertices in the tree and the number of edges to be removed.

Each of the next $$$n - 1$$$ lines of each set of input data contains two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$) — the next edge of the tree.

It is guaranteed that the sum of the values of $$$n$$$ for all sets of input data does not exceed $$$10^5$$$.

Output

For each set of input data, output a single line containing the maximum number $$$x$$$ such that it is possible to remove exactly $$$k$$$ edges from the tree in such a way that the size of each remaining connected component is at least $$$x$$$.

Example
Input
6
5 1
1 2
1 3
3 4
3 5
2 1
1 2
6 1
1 2
2 3
3 4
4 5
5 6
3 1
1 2
1 3
8 2
1 2
1 3
2 4
2 5
3 6
3 7
3 8
6 2
1 2
2 3
1 4
4 5
5 6
Output
2
1
3
1
1
2
Note

The tree in the first set of input data:

After removing the edge $$$1$$$ — $$$3$$$, the tree will look as follows:

The tree has split into two connected components. The first component consists of two vertices: $$$1$$$ and $$$2$$$. The second connected component consists of three vertices: $$$3, 4$$$ and $$$5$$$. In both connected components, there are at least two vertices. It can be shown that the answer $$$3$$$ is not achievable, so the answer is $$$2$$$.