\text{Khoảng cách đỉnh xa}

Đị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

Tèo đang xây dựng bản đồ cho khu rừng FPTOJ với \(N\) cây và \(N-1\) con đường. Có \(Q\) truy vấn, mỗi truy vấn yêu cầu đếm số lượng cây \(v\) sao cho khoảng cách từ \(u\) đến \(v\) không vượt quá \(K\).

Yêu cầu: Trả lời \(Q\) truy vấn \((u, K)\): đếm số đỉnh \(v\) thỏa \(dist(u, v) \le K\).

Đầu vào

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

Đầu ra

• In ra kết quả cho mỗi truy vấn trên một dòng.

Ví dụ

Đầu vào:

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

Đầu ra:

5
4
2

Giải thích

• (1,2): tất cả 5 đỉnh đều cách 1 không quá 2.
• (2,1): cách 2 không quá 1 gồm {2,1,4,5} — 4 đỉnh.
• (3,1): cách 3 không quá 1 gồm {3,1} — 2 đỉnh.

Subtask