题目背景

历史/落在/赢家/之手
至少/我们/拥有/传说
谁说/败者/无法/不朽
拳头/只能/让人/低头
念头/却能/让人/抬头
抬头/去看/去爱/去追
你心中的梦

题目描述

又想起了四月。

如果不是省选，大家大概不会这么轻易地分道扬镳吧？只见一个又一个昔日的队友离开了机房。

凭君莫话封侯事，一将功成万骨枯。

梦里，小 F 成了一个给将军送密信的信使。

现在，有两封关乎国家生死的密信需要送到前线大将军帐下，路途凶险，时间紧迫。小 F 没有怯战，勇敢地承担了这个任务。

不过，小 F 实在是太粗心了，他一不小心把两封密信中的一封给弄掉了。

小 F 偷偷打开了剩下的那封密信。他发现一副十分详细的地图，以及几句批文——原来这是战场周围的情报地图。他仔细看后发现，在这张地图上标记了 $n$ 个从 $1$ 到 $n$ 标号的驿站，$n - 1$ 条长度为 $1$ 里的小道，每条小道双向连接两个不同的驿站，并且驿站之间可以通过小道两两可达。

小 F 仔细辨认着上面的批注，突然明白了丢失的信的内容了。原来，每个驿站都可以驻扎一个小队，每个小队可以控制距离不超过 $k$ 里的驿站。如果有驿站没被控制，就容易产生危险——因此这种情况应该完全避免。而那封丢失的密信里，就装着数学重臣留下的精妙的排布方案，也就是用了最少的小队来控制所有驿站。

小 F 知道，如果能计算出最优方案的话，也许他就能够将功赎过，免于死罪。他找到了你，你能帮帮他吗？当然，小 F 在等待你的支援的过程中，也许已经从图上观察出了一些可能会比较有用的性质，他会通过一种特殊的方式告诉你。

输入格式

从标准输入中读入数据。

输入第 $1$ 行为三个正整数 $n,k,t$，分别代表：驿站数，一支小队能够控制的最远距离，以及对应的特殊性质的编号。关于特殊性质请参考数据范围中的表格。

输入第 $2$ 行至第 $n$ 行，每行两个正整数 $u_i,v_i$，表示在编号为 $u_i$ 和 $v_i$ 的驿站之间有一条长度为 $1$ 里的小道。

输出格式

输出到标准输出中。

输出仅包含一行一个正整数，为最优方案下需要的小队数。

4 1 0 
1 2 
1 3 
1 4

1 
 

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

2 

提示

【样例 1 说明】

如图。由于一号节点到周围的点距离均是 $1$，因此可以控制所有驿站。

【样例 2 说明】

如图，和样例 1 类似。

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。

$t$ 的含义如下：

• $t = 0$：该测试点没有额外的特殊性质；
• $t = 1$：保证最多 $8$ 个点的所连接的小道超过 $1$ 条；
• $t = 2$：保证所有点到 $1$ 号点的距离不超过 $2$。

每个测试点的数据规模及特点如下表