有一棵由n个顶点组成的树。顶点编号为 1 到 n。
让我们将区间 [l, r] 的长度定义为值 r - l + 1。这棵树的子树的分数是区间 [l, r] 的最大长度,其中编号为 l, l + 1, ..., r 的顶点属于该子树。
考虑树中大小至多为 k 的所有子树,返回子树的最大分数。请注意,在这个问题中,树没有根,因此子树是树的任意连通子图。
输入
第一行有两个整数,n 和 k (1 ≤ k ≤ n ≤ 105)。接下来的 n - 1 行中的每一行都包含整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi)。这意味着 ai 和 bi 通过树边连接。
保证输入代表一棵树。
输出
输出应包含一个整数 - 最大可能分数。
示例
输入 #1
10 6 4 10 10 6 2 9 9 6 8 5 7 1 4 7 7 3 1 8
输出 #1
3
输入 #2
16 7 13 11 12 11 2 14 8 6 9 15 16 11 5 14 6 15 4 3 11 15 15 14 10 1 3 14 14 7 1 7
输出 #2
6
注意
对于第一种情况,存在一些子树,其大小最多为6,包括3个连续的顶点数。例如,由{1,3,4,5,7,8}或{1,4,6,7,8,10}组成的子树包括3个连续的顶点。但不存在大小最大为 6 且包含 4 个或更多连续顶点的子树。