Mashmokh và Bể Nước

Cho một cây có gốc gồm $m$ đỉnh, đánh số từ $1$ đến $m$, đỉnh $1$ là gốc. Mỗi đỉnh có một bể nước, ban đầu tất cả đều rỗng.

Bạn có $k$ lít nước và $p$ đồng. Trò chơi diễn ra như sau:

• Bước chuẩn bị: chọn không quá $k$ đỉnh không phải gốc và đổ chính xác $1$ lít nước vào mỗi đỉnh được chọn.
• Sau đó lặp lại các bước dưới đây cho đến khi không còn nước trong cây:
  1. Mở cửa tất cả các bể. Sau đó chọn một số đỉnh không phải gốc để đóng cửa trong bước này. Nếu một bể chứa $w$ lít nước bị đóng cửa, bạn phải trả $w$ đồng.
  2. Sắp xếp các đỉnh theo độ sâu không giảm: $x_1,x_2,\dots ,x_m$ (với $x_1$ là gốc). Lần lượt xét từng đỉnh trong danh sách:
     • Đỉnh $x_1$ (gốc): toàn bộ nước trong gốc được lấy ra.
     • Đỉnh $x_i$ với $i>1$: nếu cửa của $x_i$ đang đóng thì bỏ qua; ngược lại, toàn bộ nước trong bể của $x_i$ chảy về bể của cha (kể cả khi cửa của cha đang đóng).

Giả sử trò chơi kết thúc sau $l$ bước, và $w_i$ là số lít nước có trong bể gốc sau bước thứ $i$. Bạn thắng $max(w_1,w_2,\dots ,w_l)$ đồng. Hỏi giá trị lớn nhất bạn có thể thắng được?

Lưu ý: số đồng dùng để đóng cửa được tính riêng cho mỗi bước — nếu cùng một bể bị đóng trong nhiều bước, bạn phải trả mỗi bước. Tổng số đồng dùng trong cả trò chơi không được vượt quá $p$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $m$, $k$, $p$.
• $m-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$, $b_i$ — một cạnh của cây.

Dữ liệu ra

In ra một số nguyên duy nhất — đáp án bài toán.

Ràng buộc

• $2\le m\le {10}^5$
• $0\le k,p\le {10}^9$
• $1\le a_i,b_i\le m$, $a_i\ne b_i$
• Dữ liệu vào luôn đảm bảo tạo thành một cây với gốc tại đỉnh $1$.

Ví dụ