CF414D.Mashmokh and Water Tanks

Mashmokh is playing a new game. In the beginning he has k liters of water and p coins. Additionally he has a rooted tree (an undirected connected acyclic graph) that consists of m vertices. Each vertex of the tree contains a water tank that is empty in the beginning.

The game begins with the fact that Mashmokh chooses some (no more than k) of these tanks (except the root) and pours into each of them exactly 1 liter of water. Then the following process is performed until there is no water remained in tanks.

• The process consists of several steps.
• At the beginning of each step Mashmokh opens doors of all tanks. Then Mashmokh closes doors of some tanks (he is not allowed to close door of tank in the root) for the duration of this move. Let's denote the number of liters in some tank with closed door as w, Mashmokh pays w coins for the closing of that tank during this move.
• Let's denote by _x_1, _x_2, ..., x__m as the list of vertices of the tree sorted (nondecreasing) by their depth. The vertices from this list should be considered one by one in the order. Firstly vertex _x_1 (which is the root itself) is emptied. Then for each vertex x__i (i > 1), if its door is closed then skip the vertex else move all the water from the tank of vertex x__i to the tank of its father (even if the tank of the father is closed).

Suppose l moves were made until the tree became empty. Let's denote the amount of water inside the tank of the root after the i-th move by w__i then Mashmokh will win max(_w_1, _w_2, ..., w__l) dollars. Mashmokh wanted to know what is the maximum amount of dollars he can win by playing the above game. He asked you to find this value for him.

马什莫赫正在玩一个新游戏。游戏开始时，他有 $k$ 升水和 $p$ 枚硬币。此外，他还拥有一棵有根树（即一个无向、连通、无环的图），该树包含 $m$ 个顶点。树中每个顶点上均有一个水箱，初始时所有水箱均为空。

游戏开始时，马什莫赫从除根节点外的所有顶点中任选若干个（至多 $k$ 个）水箱，并向每个选中的水箱中恰好倒入 1 升水。随后，执行以下过程，直至所有水箱中均无剩余水量为止：

• 该过程由若干轮（steps）组成。

• 每轮开始时，马什莫赫打开所有水箱的门；接着，他可选择关闭其中某些水箱的门（但不允许关闭根节点水箱的门），该关闭操作仅持续本轮。若某水箱当前水量为 $w$ 升且其门被关闭，则马什莫赫需为此支付 $w$ 枚硬币。

• 将树中所有顶点按深度非递减顺序排序，记为 $x_1,\,x_2,\,\dots,\,x_m$。然后依次处理该序列中的每个顶点：

  • 首先清空顶点 $x_1$（即根节点）中的全部水量；
  • 对于每个后续顶点 $x_i$（其中 $i > 1$）：若其门处于关闭状态，则跳过该顶点；否则，将其水箱中的全部水量转移至其父节点的水箱中（即使父节点水箱的门处于关闭状态，水量仍会转移过去）。

假设整个过程共进行了 $l$ 轮，记第 $i$ 轮结束后根节点水箱中的水量为 $w_i$，则马什莫赫最终赢得 $\max(w_1,\,w_2,\,\dots,\,w_l)$ 美元。马什莫赫想知道：在上述规则下，他最多能赢得多少美元？请你帮他求出该最大值。

The first line of the input contains three space-separated integers m, k, p (2 ≤ m ≤ 105; 0 ≤ k, p ≤ 109).

Each of the following m - 1 lines contains two space-separated integers a__i, b__i (1 ≤ a__i, b__i ≤ m; a__i ≠ b__i) — the edges of the tree.

Consider that the vertices of the tree are numbered from 1 to m. The root of the tree has number 1.

输入的第一行包含三个用空格分隔的整数 $m$、$k$、$p$（$2 \leq m \leq 10^5$；$0 \leq k, p \leq 10^9$）。

接下来的 $m - 1$ 行，每行包含两个用空格分隔的整数 $a_i$、$b_i$（$1 \leq a_i, b_i \leq m$；$a_i \neq b_i$），表示树的边。

假设树的顶点编号为 $1$ 到 $m$。树的根节点编号为 $1$。

Output a single integer, the number Mashmokh asked you to find.

输出一个整数，即 Mashmokh 要求你找出的数。

The tree in the first sample is shown on the picture below. The black, red, blue colors correspond to vertices with 0, 1, 2 liters of water.

One way to achieve the maximum amount of money is to put 1 liter of water in each of vertices 3 and 4. The beginning state is shown on the picture below.

Then in the first move Mashmokh will pay one token to close the door of the third vertex tank. The tree after the first move is shown on the picture below.

After the second move there are 2 liters of water in the root as shown on the picture below.

第一个样例中的树如下图所示。黑色、红色、蓝色分别对应水量为 0、1、2 升的顶点。

一种实现最大收益的方法是在顶点 3 和顶点 4 中各放入 1 升水。初始状态如下图所示。

接着，在第一步中，Mashmokh 将花费 1 枚代币关闭顶点 3 的水箱门。第一次操作后的树如下图所示。

第二次操作后，根节点中将有 2 升水，如下图所示。