Vertex Spacing

Một cây là một đồ thị liên thông và không chứa bất kỳ chu trình nào.

Khoảng cách giữa hai đỉnh của cây là độ dài (tính bằng số cạnh) của đường đi ngắn nhất nối giữa hai đỉnh đó.

Cho một cây gồm $n$ đỉnh và một số nguyên dương $k$. Hãy xác định số lượng cặp đỉnh phân biệt có khoảng cách giữa chúng đúng bằng $k$. Hai cặp $(u, v)$ và $(v, u)$ được coi là cùng một cặp.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1 ≤ n ≤ 50000$, $1 ≤ k ≤ 500$), lần lượt biểu thị số lượng đỉnh của cây và khoảng cách yêu cầu giữa các đỉnh.

Trong $n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$ ($1 ≤ a_i, b_i ≤ n$, $a_i ≠ b_i$) mô tả một cạnh nối trực tiếp giữa hai đỉnh $a_i$ và $b_i$. Tất cả các cạnh được cho đều phân biệt.

Kết quả

In ra một số nguyên duy nhất, biểu thị số lượng cặp đỉnh phân biệt của cây có khoảng cách giữa chúng đúng bằng $k$.

Chấm điểm

Subtask 1 (30 points). $n ≤ 2000$

Subtask 2 (70 points). $1 ≤ n ≤ 50000$

Ví dụ

Input

5 2
1 2
2 3
3 4
2 5

Output

4

Ghi chú

Trong ví dụ mẫu, các cặp đỉnh có khoảng cách bằng $2$ gồm có $(1, 3)$, $(1, 5)$, $(3, 5)$ và $(2, 4)$.