Một ngân hàng có n chi nhánh, mỗi chi nhánh có một máy chủ, các máy chú ở các chi nhánh được đánh số từ 1 đến n. Nhằm bảo đảm việc truyền thông giữa các chi nhánh, ngân hàng đã thuê n - 1 kênh truyền tin trực tiếp từ một nhà cung cấp dịch vụ mạng để kết nối n máy chủ thành một mạng máy tính và bảo đảm từ máy chủ của một chi nhánh bắt kì có thể truyền tin đến tất cả các máy chủ của các chi nhánh còn lại theo kênh truyền tin trực tiếp giữa chúng hoặc thông qua đường truyền đi qua một số máy chú của các chi nhánh nảo đó.

Trong thời gian tới, ngân hàng muốn lựa chọn k máy chủ trong n máy chú để cài đặt phần mềm kiểm soát. Phần mềm khi hoạt động sẽ làm tăng lưu lượng truyền trên các kênh giữa k máy chủ này. Với mỗi phương án chọn k máy chủ đề cải đặt phần mềm, trong số n - 1 kênh truyền tin, nhà cung cấp dịch vụ mạng đã xác định một số ít nhất các kênh đủ để kết nối k máy chú này và khuyến cáo ngân hàng cần phải nâng cấp các kênh đó. Vì Ií do kĩ thuật cũng như kinh phí, ngân hàng muốn lựa chọn k máy chú để cài đặt phần mềm mà số lượng kênh ít nhất cần nâng cấp có giá trị nằm trong đoạn [a, b]. Cụ thể, với một cách chọn k máy chủ, gọi s là số kênh ít nhất cần chọn ra trong n - 1 kênh truyền tin nhằm bảo đảm liên thông giữa k máy chủ được chọn ngay cả khi các kênh còn lại bị đứt kết nối, s kênh này sẽ được khuyến cáo nâng cấp, khi đó, cách chọn k máy chủ thoa măn yêu cầu của ngân hàng nếu a ≤ s ≤ b.

Yêu cầu: Cho n - 1 kênh truyền tin và các giá trị k,a,b, hãy đếm số lượng cách chọn k máy chủ để cài đặt phần mềm mà số lượng kênh ít nhất cần nâng cấp nằm trong đoạn [a, b].

Dữ liệu: Vào từ file văn bản COMNET.INP:

• Dòng thứ nhất chứa bốn số nguyên dương n, k, a, b (k < n; 1 < a <= b < n)

• Dòng thứ i trong số n - 1 dòng tiếp theo chứa hai số nguyên dương u1, v1, cho biết có kênh truyền tin trực tiếp giữa hai máy chủ ui, vi, (1 <= ui, vi <= n; ui khác vi).

Các số trên cùng một dòng cách nhau bởi đầu cách.

Kết quả: Ghi ra file văn bản COMNET.OUT một số nguyên duy nhất là số cách chọn k để cài đặt phần mềm thóa mẫn yêu cầu của ngân hàng.

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bải thoa mẫn: n ≤ 100 và k = 2;

• 30% số test khác ứng với 30% số điểm của bải thóa mãn: n ≤ 100 và k = 3;

• 20% số test khác ứng với 20% số điểm của bải thóa mẫn: n ≤ 100 và k = 4;

• 20% số test khác ứng với 20% số điểm của bải thóa măn: n ≤ 1000 và k = 3;

• 10% số test còn lại ứng với 10% số điểm của bài thóa mãn: n ≤ 1000 và k = 4.

Input:

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

Output:

14

Cô 5 cách chọn 3 máy chủ trong 6 mãy chú mà Bố kênh cần nâng cấp bằng 2 là:（1, 2, 3）;（2, 3, 4）;（2, 3, 6）;（3, 4, 5）;（3, 4, 6)

Có 9 cách chọn 3 máy chủ trong 6 máy chủ mà số kênh cần nâng cấp bằng 3: (1, 2, 4) ; (1, 2, 6) ; (1, 3, 4) ; (1, 3, 6) ; (2, 3, 5) ; (2, 4, 5) ; (2, 4, 6) ; (3, 5, 6) ; (4, 5, 6)

Như vậy, có tất cá 14 cách chọn 3 máy chủ trong 6 máy chủ thóa măn yêu cầu của ngân hàng.