Tý cần giải bài toán sau:

Trong khu rừng FPTOJ có \(N\) cây được nối với nhau bởi \(N-1\) con đường, mỗi con đường có độ dài \(w_i\). Các nhà thám hiểm muốn biết có bao nhiêu cặp cây \((u, v)\) mà đường đi giữa chúng có tổng độ dài chính xác bằng \(K\).

Yêu cầu: Đếm số cặp đỉnh \((u, v)\) (\(u < v\)) sao cho \(dist(u, v) = K\).

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Đầu vào

• Dòng đầu tiên chứa hai số nguyên \(N, K\) (\(1 \le N \le 10^5\), \(1 \le K \le 10^6\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le w \le 10^6\)).

Đầu ra

• In ra một số nguyên duy nhất là số cặp thỏa mãn.

Ví dụ

Đầu vào:

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

Đầu ra:

2

Giải thích

Các cặp có tổng khoảng cách bằng 4: \((1, 3)\) (\(1+3=4\)) và \((5, 2)\) (\(2+2=4\)). Vậy có 2 cặp.

Subtask