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 \(\text{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