题目描述

奶牛们建立了一个电话网络，对于这个题目可以将其视为一个有 $N$（$1 \le N \le 100{,}000$）个结点的无根树，为了方便将其编号为 $1\cdots N$。每个结点代表一个电话交换机，每条边代表用于连接两个交换机的电话线。第 $i$ 条边由该边连接的两个结点 $A_i$ 和 $B_i$ 表示（$1 \le A_i \le N, 1 \le B_i \le N, A_i \ne B_i$）。

有些交换机只有一条电话线连接到另一个交换机，这些是树的叶子结点，每个叶子结点都是一个位于奶牛田中的电话亭。

两只奶牛交流时的对话沿着两个奶牛所在节点之间的唯一的最短路径传递。一个交换机最多可以同时处理 $K$（$1 \le K \le 10$）个对话，并且在任何时候每个电话线上最多只能有一个对话。

假设每个叶子结点上都有一头奶牛，那么最多有多少对奶牛可以同时进行对话？当然，一头奶牛最多只能参与一个对话。

输入格式

第 $1$ 行：两个由空格分隔的整数 $N$ 和 $K$。

第 $2\cdots N$ 行：第 $i + 1$ 行包含两个由空格分隔的整数 $A_i$ 和 $B_i$。

输出格式

第 $1$ 行：可以同时进行对话的奶牛对数。

6 1 
1 2 
2 3 
2 4 
4 5 
4 6 

2 

提示

1   5          C1   C5 
|   |          ||   || 
2---4   -->    |2---4| 
|   |          ||   || 
3   6          C3   C6

考虑这个有 $6$ 个结点且 $K = 1$ 的电话树：

有四头分别位于节点 $1$、$3$、$5$ 和 $6$ 的奶牛。如果奶牛 $1$ 和奶牛 $3$ 交谈，奶牛 $5$ 和奶牛 $6$ 交谈，那么它们不会超过每个交换机的最大对话数，所以在这个样例中答案是 $2$（即有两对奶牛可以同时进行交谈）。