D. 研发基地 / hub
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

Input

从标准输入读入数据。

本题包含多组测试数据。

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

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

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

输出到标准输出。

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

Example
Input
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
Output
1
2
Note

补充样例文件可从原题页面的附件下载：https://www.luogu.com.cn/problem/P17834。

样例 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)$$$ 构成一棵树。
测试点编号$$$n\le$$$$$$N\le$$$$$$k\le$$$特殊性质
$$$1$$$$$$5$$$$$$15$$$$$$5$$$无
$$$2,3$$$$$$10$$$$$$30$$$$$$10$$$无
$$$4\sim 6$$$$$$100$$$$$$300$$$$$$100$$$无
$$$7$$$$$$1000$$$$$$3000$$$$$$2$$$无
$$$8$$$$$$1000$$$$$$3000$$$$$$1000$$$无
$$$9,10$$$$$$4000$$$$$$10^4$$$$$$4000$$$无
$$$11,12$$$$$$10^5$$$$$$3\times 10^5$$$$$$2$$$无
$$$13,14$$$$$$10^5$$$$$$3\times 10^5$$$$$$10^5$$$A
$$$15$$$$$$5\times 10^5$$$$$$10^6$$$$$$10$$$无
$$$16,17$$$$$$5\times 10^5$$$$$$10^6$$$$$$5\times 10^5$$$无
$$$18\sim 20$$$$$$10^6$$$$$$2\times 10^6$$$$$$10^6$$$无

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

本题满分 100 分。官方测试点共 20 个，每个测试点 5 分，独立计分。展示样例中，与官方测试点完全相同的样例保留原测试点分值；其余样例不计分。