Quân khám phá Sài Gòn

Quân vừa nhập học ngành Khoa học Máy tính và tham gia Câu lạc bộ Khám phá Sài Gòn – nơi mọi người cùng nhau khám phá những con hẻm, quán xá và địa điểm thú vị trong thành phố. Mỗi tuần, CLB lại tổ chức một chuyến đi ngẫu nhiên, nhưng có một quy tắc: mỗi hành trình phải đi qua đúng \(k\) đoạn đường, không được quay lại nơi đã đến.

Quân được giao nhiệm vụ xem xét các hành trình thỏa mãn điều kiện trên. Bản đồ các địa điểm mà CLB muốn khám phá được kết nối như một đồ thị cây với \(n\) địa điểm (được đánh số từ \(1\) đến \(n\)) và \(n - 1\) đường đi giữa các địa điểm; mỗi hành trình là một đường đi gồm chính xác \(k\) đoạn đường (cạnh), các đỉnh không trùng nhau.

Yêu cầu: Là người bạn đồng hành đáng tin cậy của Quân, bạn hãy giúp Quân đếm số lượng đường đi khác nhau có độ dài chính xác \(k\) đoạn đường.

Input

• Dòng đầu tiên chứa \(2\) số nguyên \(n\) và \(k\): số lượng đỉnh và độ dài của hành trình (\(1 \le k \le n \le 2 \cdot 10^5\)).
• Sau đó là \(n - 1\) dòng, mỗi dòng chứa \(2\) số nguyên \(a\) và \(b\), cho biết tồn tại một đoạn đường giữa \(2\) địa điểm \(a\) và \(b\) (\(1 \le a, b \le n\)).

Output

In ra số đường đi thỏa mãn.

Scoring

• Subtask 1: \(n \le 5000\).
• Subtask 2: Cây có dạng đường thẳng.
• Subtask 3: Không có ràng buộc nào thêm.

Sample Input 1

5 2
1 2
2 3
3 4
3 5

Sample Output 1

4

Notes

Hành trình \((u, v)\) và \((v, u)\) chỉ được tính một lần.