题目描述

某地区有 $n$ 个村庄，编号为 $1, 2, \dots, n$，由 $n-1$ 条道路连成一棵树，每条道路长度为 $1$。巡警车每天从编号 $1$ 的警察局出发，遍历所有道路后返回警察局。

为了缩短巡逻路线，地区计划新建 $K$ 条道路（$K=1$ 或 $K=2$），每条新道路可连接任意两个村庄（包括同一个村庄的自环），且巡警车必须恰好经过每条新建道路一次。请计算新建 $K$ 条道路后能达到的最小巡逻距离。

下图展示了一个有 $8$ 个村庄的地区（村庄 $1$ 为黑色），原始巡逻需走 $14$ 个单位距离。

在方案 (a) 中新建一条道路，总距离降为 $11$；方案 (b) 新建两条道路，总距离为 $10$；方案 (c) 新建两条道路但总距离反升至 $15$。

输入格式

第一行包含两个整数 $n$ 和 $K$（$1 \le K \le 2$）。

接下来 $n-1$ 行，每行两个整数 $a,b$，表示村庄 $a$ 与 $b$ 之间有一条道路（$1 \le a,b \le n$）。

输出格式

输出一个整数，表示新建 $K$ 条道路后能达到的最小巡逻距离。

样例

8 1 
1 2 
3 1 
3 4 
5 3 
7 5 
8 5 
5 6

11

8 2 
1 2 
3 1 
3 4 
5 3 
7 5 
8 5 
5 6

10

5 2 
1 2 
2 3 
3 4 
4 5

6

提示

• $10\%$ 的数据中，$1 \le n \le 1000, K=1$；
• $30\%$ 的数据中，$K=1$；
• $80\%$ 的数据中，每个村庄相邻的村庄数不超过 $25$；
• $90\%$ 的数据中，每个村庄相邻的村庄数不超过 $150$；
• $100\%$ 的数据中，$3 \le n \le 10^5, 1 \le K \le 2$。