[AdditionalFile5500.zip](file://AdditionalFile5500.zip?type=additional_file)

#5500. 「POI2006 R2」地铁 Metro

标签: 传统 | 时间限制: 4500 ms | 内存限制: 128 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – II etap Metro

某座城市在修建地铁时长期面临困境。在此期间，资金管理不善，建设成本被低估，而且还忘记为购买列车预留资金。结果是，虽然建成了许多车站，但只挖掘了计划中的部分隧道，仅仅足够保证任意两个车站之间可以通行。隧道的数量比建成的车站数量少 $1$，此外，所有隧道都是双向的。用剩余的资金，他们只买得起几辆列车。

为了挽回颜面，地铁管理部门向你求助，希望你能够设计列车的运行路线，使得尽可能多的车站能够被地铁线路覆盖。每辆列车都必须沿着一条固定的路线行驶。路线必须是简单的，也就是说，不能有分支（在同一个车站交汇的三条隧道不能同时属于同一条路线）。不过，多条路线可以经过同一个车站或同一条隧道。

你的任务是编写一个程序，该程序：

• 从标准输入读取隧道网络描述以及需要规划的地铁列车路线数量；
• 计算出在要求的路线数量下，最多可以有多少个车站被覆盖；
• 将结果写入标准输出。

输入格式

输入的第一行包含两个整数 $n$ 和 $l$ $(2 \le n \le 1000000, 0 \le l \le n)$，由单个空格隔开。$n$ 是车站的数量，$l$ 是需要规划的列车路线数量。车站编号从 $1$到 $n$。

接下来的 $n-1$ 行中，每行都包含两个不同的整数，由单个空格隔开。第 $i+1$ 行的两个数字 $a_i, b_i$ $(1 \le a_i, b_i \le n)$ 是第 $i$ 条隧道所连接的车站编号。

输出格式

输出的第一行且仅一行应包含一个整数，等于列车路线上最多可以覆盖的车站数量。

样例

输入

17 3
1 2
3 2
2 4
5 2
5 6
5 8
7 8
9 8
5 10
10 13
13 14
10 12
12 11
15 17
15 16
15 10

输出

13

图中展示了隧道网络以及在一种最优布局下的地铁路线标记。