给你一棵有 $$$n$$$ 个顶点的树。
你的任务是找到最大数量$$$x$$$,这样就可以从这棵树中精确删除$$$k$$$边,使得每个剩余连接组件$$$^{\dagger}$$$的大小至少为$$$x$$$。
$$$^{\dagger}$$$ 如果存在任意长度 $$$k$$$ 的数字序列 $$$t_1, t_2, \ldots, t_k$$$,则两个顶点 $$$v$$$ 和 $$$u$$$ 位于同一连通分量中,使得 $$$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$$$。
示例
输入 #1
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
输出 #1
2 1 3 1 1 2
注意
第一组输入数据中的树:
删除边 $$$1$$$ — $$$3$$$ 后,树将如下所示:
树已分裂为两个连接的组件。第一个组件由两个顶点组成:$$$1$$$ 和 $$$2$$$。第二个连通分量由三个顶点组成:$$$3、4$$$ 和 $$$5$$$。在两个连通分量中,至少有两个顶点。可以看出,答案$$$3$$$是无法实现的,所以答案是$$$2$$$。