小 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}\operatorname{dist}(i,j)，其中 \operatorname{dist}(i,j) 表示从第 i 座城市到第 j 座城市所需经过的道路的最少条数。特别地，若 i\in S，则 d(i)=0。定义该建造方案的通勤半径为所有城市通勤距离的最大值，即 \max_{i=1}^{n}d(i)。

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

从文件 hub.in 中读入数据。

本题包含多组测试数据。

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

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

• 第一行包含两个正整数 n,k，分别表示城市数量和小 W 计划建造的研发基地数量。
• 第 i+1\ (1\le i\le n-1) 行包含两个正整数 u_i,v_i，分别表示第 i 条道路连接的两座城市的编号。

输出到文件 hub.out 中。

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

样例 1 解释

该样例共包含两组测试数据。

对于第一组测试数据，共有 10 种合理的建造方案。按通勤半径分类如下：

• 通勤半径为 1 的方案：S={1,4}，S={2,4}，S={2,5}；
• 通勤半径为 2 的方案：S={1,3}，S={1,5}，S={2,3}，S={3,4}，S={3,5}；
• 通勤半径为 3 的方案：S={1,2}，S={4,5}。

因此，所有合理的建造方案的通勤半径的最小值为 1。

对于第二组测试数据，一种合理的建造方案为 S={2,7,9}，其中第 2 座城市单独构成一个连通块，第 7 座和第 9 座城市构成一个连通块。该建造方案的通勤半径为 2。

样例 2

见题目目录下的 hub/2.in 与 hub/2.ans。

该样例满足测试点 2,3 的约束条件。

样例 3

见题目目录下的 hub/3.in 与 hub/3.ans。

该样例满足测试点 8 的约束条件。

样例 4

见题目目录下的 hub/4.in 与 hub/4.ans。

该样例满足测试点 11,12 的约束条件。

样例 5

见题目目录下的 hub/5.in 与 hub/5.ans。

该样例满足测试点 13,14 的约束条件。

数据范围

设 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) 构成一棵树。

特殊性质 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。

CSP-S 2026