题目描述

小 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$ 座城市的通勤距离为 $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 求出，所有合理的建造方案的通勤半径的最小值。

输入格式

本题包含多组测试数据。

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

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

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

输出格式

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

样例 1

0 2
5 2
1 2
2 3
3 4
4 5
10 3
1 2
1 3
2 4
2 5
3 6
3 7
3 8
7 9
9 10

1
2

说明

样例 1 解释：第一组共有 10 种合理的建造方案。通勤半径为 1 的方案有 $S = \{1, 4\}$、$\{2, 4\}$、$\{2, 5\}$；通勤半径为 2 的方案有 $\{1, 3\}$、$\{1, 5\}$、$\{2, 3\}$、$\{3, 4\}$、$\{3, 5\}$；通勤半径为 3 的方案有 $\{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$；
• 所有 $(u_i, v_i)$ 构成一棵树。

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

本题需要文件读写：输入文件 hub.in，输出文件 hub.out。

来源：CSP-S 2026 第二轮 T4。本 OJ 的测试数据为按题面测试点表自造，不是官方数据。本 OJ 内存上限为 512 MiB（原题 1024 MiB）。