Description

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

题目描述

给定一个包含 $n$ 个顶点的树。

你的任务是找到最大的数字 $x$，使得可以从这棵树中移除恰好 $k$ 条边，以便每个剩余连通块的大小至少为 $x$。

两个顶点 $v$ 和 $u$ 属于同一个连通块，如果存在任意长度 $k$ 的序列 $t_1, t_2, \ldots, t_k$，满足 $t_1 = v$，$t_k = u$，且对于 $1$ 到 $k - 1$ 之间的每个 $i$，顶点 $t_i$ 和 $t_{i+1}$ 由一条边相连。

输入

每个测试包含多组输入数据。第一行包含一个整数 $t$ ($1 \le t \le 10^4$) — 输入数据组数。接下来是每组输入数据的描述。

每组输入数据的第一行包含两个整数 $n$ 和 $k$ ($1 \le k < n \le 10^5$) — 树中顶点数和要移除的边数。

接下来每组输入数据的 $n - 1$ 行，每行包含两个整数 $v$ 和 $u$ ($1 \le v, u \le n$) — 树的下一条边。

保证所有输入数据的 $n$ 的总和不超过 $10^5$。

输出

对于每组输入数据，输出一个数字 $x$，表示可以从树中移除恰好 $k$ 条边的最大数字 $x$，使得每个剩余连通块的大小至少为 $x$。

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

2
1
3
1
1
2

提示

第一组输入数据中的树：

移除边 $1$ — $3$ 后，树将变为：

树分裂成两个连通块。第一个连通块包含两个顶点：$1$ 和 $2$。第二个连通块包含三个顶点：$3, 4$ 和 $5$。在两个连通块中，至少有两个顶点。可以证明答案不可能是 $3$，因此答案应为 $2$。