Mashmokh 正在玩一个新游戏。一开始他有 k 升水和 p 个硬币。此外,他还有一棵由 m 个顶点组成的有根树(无向连接的无环图)。树的每个顶点都包含一个水箱,该水箱一开始是空的。
游戏开始时,Mashmokh 选择一些(不超过 k)个水箱(除了根)并向每个水箱中倒入 1 升水。然后执行以下过程,直到水箱中没有水为止。
- 该过程由几个步骤组成。
- 在每一步开始时,Mashmokh都会打开所有坦克的门。然后,Mashmokh 在此移动期间关闭一些坦克的门(不允许他在根部关闭坦克的门)。我们将某个关着门的水箱中的升数表示为 w,Mashmokh 在此移动过程中为关闭该水箱支付 w 个硬币。
- 让我们用 x1, x2, ..., xm 表示按深度排序(非递减)的树顶点列表。应按顺序一一考虑此列表中的顶点。首先,顶点 x1(即根本身)被清空。然后对于每个顶点 xi (i > 1),如果它的门关闭,则跳过该顶点,否则将所有水从顶点 xi 的水箱移动到其父亲的水箱(即使父亲的水箱关闭)。
假设进行了 l 次移动,直到树变空。让我们用 wi 来表示第 i 次移动后根池内的水量,那么 Mashmokh 将赢得 max(w1, w2, ..., wl) 美元。 Mashmokh 想知道通过玩上述游戏他最多可以赢得多少美元。他要求你为他找到这个价值。
输入
输入的第一行包含三个空格分隔的整数 m、k、p(2 ≤ m ≤ 105;0 ≤ k、p ≤ 109)。
以下 m - 1 行中的每一行都包含两个以空格分隔的整数 ai, bi (1 ≤ ai, bi ≤ m; ai ≠ bi) — 树的边。
考虑树的顶点编号从 1 到 m。树的根编号为 1。
输出
输出一个整数,即 Mashmokh 要求您查找的数字。
示例
输入 #1
10 2 1 1 2 1 3 3 4 3 5 2 6 6 8 6 7 9 8 8 10
输出 #1
2
输入 #2
5 1000 1000 1 2 1 3 3 4 3 5
输出 #2
4
注意
第一个示例中的树如下图所示。黑色、红色、蓝色分别对应有 0、1、2 升水的顶点。
获得最大金钱量的一种方法是在顶点 3 和 4 中各放入 1 升水。开始状态如下图所示。
然后在第一步中,Mashmokh 将支付一个代币来关闭第三个顶点坦克的门。第一次移动后的树如下图所示。
第二次移动后,根部有2升水,如下图所示。