Phòng cách đều

Cho một cây gồm $n$ đỉnh được đánh số từ $1$ đến $n$ và $n-1$ cạnh. Khoảng cách giữa hai đỉnh là số cạnh trên đường đi ngắn nhất nối chúng.

Có $m$ truy vấn, mỗi truy vấn cho hai đỉnh $x$ và $y$ (có thể trùng nhau). Với mỗi truy vấn, hãy đếm số đỉnh $v$ của cây có khoảng cách từ $v$ đến $x$ bằng khoảng cách từ $v$ đến $y$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i,b_i$ mô tả một cạnh nối hai đỉnh $a_i$ và $b_i$. Dữ liệu đảm bảo các cạnh tạo thành một cây.
• Dòng tiếp theo chứa số nguyên $m$.
• $m$ dòng tiếp theo, dòng thứ $j$ chứa hai số nguyên $x_j,y_j$.

Dữ liệu ra

In ra $m$ dòng, dòng thứ $j$ là số đỉnh cách đều $x_j$ và $y_j$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i,b_i\le n$
• $1\le m\le {10}^5$
• $1\le x_j,y_j\le n$

Ví dụ