题目描述

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

小 W 计划选择恰好 $k$ 座城市，在每座选中的城市里各建造一个研发基地。为了便于协作，选中的城市在 $T$ 中对应的点须形成不超过两个连通块。

形式化地，建造方案 $S\subseteq\{1,2,\ldots,n\}$ 是合理的，当且仅当 $|S|=k$，且 $S$ 在 $T$ 中形成的连通块数量不超过 $2$。

对于合理的建造方案 $S$，定义第 $i$ 座城市的通勤距离为

其中 $\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$，分别表示城市数量和计划建造的研发基地数量。
• 接下来 $n-1$ 行，第 $i$ 行包含两个正整数 $u_i,v_i$，表示第 $i$ 条道路连接的两座城市的编号。

输出格式

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

样例

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

数据范围

设 $N$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试数据，$0\le c\le20$，$1\le t\le5$，$2\le n\le10^6$，$N\le2\times10^6$，$2\le k\le n$，$1\le u_i,v_i\le n$，且所有道路构成一棵树。

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