Mạng truyền thông

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ì lí 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ủ thỏa mãn yêu cầu của ngân hàng nếu $a\le s\le 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

• Dòng thứ nhất chứa bốn số nguyên dương $n,k,a,b$ $(k<n;1<a\le b<n)$;
• Dòng thứ $i$ trong số $n-1$ dòng tiếp theo chứa $2$ số nguyên dương $u_i,v_i$ cho biết có kênh truyền tin trực tiếp giữa hai máy chủ $u_i,v_i$ $(1\le u_i,v_i\le n,u_i\ne v_i)$.

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

Dữ liệu ra

In ra một số nguyên duy nhất là số cách chọn $k$ máy chủ để 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

• $k<n\le 1000$; $2\le k\le 4$.
• $1<a\le b<n$.
• $1\le u_i,v_i\le n$, $u_i\ne v_i$; $n-1$ kênh kết nối tất cả các máy chủ.

Subtasks

• Subtask 1 ($20\%$ số điểm): $n\le 100$ và $k=2$.
• Subtask 2 ($30\%$ số điểm): $n\le 100$ và $k=3$.
• Subtask 3 ($20\%$ số điểm): $n\le 100$ và $k=4$.
• Subtask 4 ($20\%$ số điểm): $n\le 1000$ và $k=3$.
• Subtask 5 ($10\%$ số điểm): $n\le 1000$ và $k=4$.

Ví dụ