小 W 曾是一名科研爱好者。在 C 国工作时，他担任测试员，日复一日地测试各种新型传送门，在城市之间来回穿梭。久而久之，他厌倦了这样的生活，于是辞去工作，来到没有任何传送门的 D 国，希望在这里重新找回对研发的热爱。

在开始研发之前，小 W 需要建造研发基地。D 国共有 n 座城市，编号为 1 到 n。这 n 座城市由 n - 1 条道路连接，其中第 i（1 \le i \le n - 1）条道路连接第 u_i 座和第 v_i 座城市。若将每座城市视作一个点，将每条道路视作连接两个点的边，则这 n 座城市和 n - 1 条道路构成一棵树 T。

小 W 的经费有限，他计划选择恰好 k 座城市，在每座选中的城市里各建造一个研发基地。为了便于这些基地之间的协作，小 W 希望选中的城市在 T 中对应的点形成不超过两个连通块。形式化地，定义建造方案 S \subseteq \{1, 2, \ldots, n\} 是合理的，当且仅当 |S| = k，且 S 在 T 中形成的连通块数量不超过 2。

对于合理的建造方案 S，定义第 i（1 \le i \le n）座城市的通勤距离为 d(i) = \min_{j \in S} \mathrm{dist}(i, j)，其中 \mathrm{dist}(i, j) 表示从第 i 座城市到第 j 座城市所需经过的道路的最少条数。特别地，若 i \in S，则 d(i) = 0。定义该建造方案的通勤半径为所有城市通勤距离的最大值，即 \max_{i=1}^{n} d(i)。

你需要帮助小 W 求出，所有合理的建造方案的通勤半径的最小值。

本题包含多组测试数据。

输入的第一行包含两个非负整数 c, t，分别表示测试点编号与测试数据组数。特别地，若 c = 0，则该测试点为样例。

接下来依次输入 t 组测试数据。对于每组测试数据：

• 第一行包含两个正整数 n, k，分别表示城市数量和小 W 计划建造的研发基地数量。

• 第 i + 1（1 \le i \le n - 1）行包含两个正整数 u_i, v_i，分别表示第 i 条道路连接的两座城市的编号。

对于每组测试数据，输出一行一个非负整数，表示所有合理的建造方案的通勤半径的最小值。

样例 1 解释：第一组数据是一条 5 个点的路 1 - 2 - 3 - 4 - 5，共有 10 种合理方案。按通勤半径分类：

• 半径为 1 的方案：S = \{1,4\},\{2,4\},\{2,5\}；

• 半径为 2 的方案：S = \{1,3\},\{1,5\},\{2,3\},\{3,4\},\{3,5\}；

• 半径为 3 的方案：S = \{1,2\},\{4,5\}。

所以最小值为 1。第二组数据的一种合理方案是 S = \{2,7,9\}，其中第 2 座城市单独构成一个连通块，第 7、9 座城市构成另一个连通块，通勤半径为 2。

数据范围：设 N 为单个测试点内所有测试数据的 n 的和。对于所有测试数据，均有：

• 0 \le c \le 20，1 \le t \le 5；

• 2 \le n \le 10^6，N \le 2 \times 10^6，2 \le k \le n；

• 对于所有 i（1 \le i \le n - 1），均有 1 \le u_i, v_i \le n，且所有 (u_i, v_i) 构成一棵树。

本题共 20 个等分测试点，每点 5 分。

特殊性质 A：存在正整数 m 满足 n = 2m + 1，且对于所有 i（1 \le i \le m），均有 u_i = i、v_i = i + 1；对于所有 i（m + 1 \le i \le n - 1），均有 u_i = i - m、v_i = i + 1。

附加样例：官方题面另有样例 3 ~ 5 三组大样例（分别满足测试点 8、11,12、13,14 的约束），因数据量较大未在此列出。

提示

答案有单调性：半径越大越容易满足，先二分通勤半径 R，再判定可行性。

判定「是否存在不超过两个连通块的方案使半径 \le R」时，注意两个化简：

• 「恰好 k 座」可以放松成「不超过 k 座」：基地所在的连通块可以沿树一条一条地把多余的名额补上去，块数不会增加。

• 固定其中一个连通块里随便一个点 root 作为根，这个块一定是「前缀封闭」的：若某个子树被选中，那么它到 root 的整条路径都被选中。

于是被剪掉的只能是「完整的高度 \le R 的子树」：以 root 为根时，若某个儿子方向的子树高度 \ge R，就必须走进这个儿子。所以每个点都对应唯一的最小块（从它出发沿「必须走」的边走到的点集），用一次换根 DP 求出每个方向的子树高度，就能线性地算出「单块」的最小结法。

两块的情形：两个块之间一定隔着若干条边，取它们之间路径的中间那条边把树切成两个连通块，可以证明两侧各自的最小块之和不会超过原来的方案。因此判定式可以写成 \min\big(\mathrm{g}(T),\ \min_{\text{割边 } e} \mathrm{g}(C_1) + \mathrm{g}(C_2)\big) \le k，其中 \mathrm{g}(C) 是「只在连通块 C 内部选点」时的最小结法数。对 n \le 1000 的数据，直接枚举割边就能拿到测试点 1 ~ 8。