Để hỗ trợ TP.Hồ Chí Minh dập dịch trong đợt cao điểm dịch bệnh Covid19 vừa qua, một đoàn y bác sĩ từ miền Bắc đã được điều vào để hỗ trợ. Tuy nhiên, hệ thống đường đi ở TP.Hồ Chí Minh khá phức tạp. Vì thế, lãnh đạo TP.Hồ Chí Minh đã nhờ các lập trình viên tạo ra 1 hệ thống hướng dẫn đường đi tự động cho các y bác sĩ.

Để đơn giản hóa việc tìm đường bằng hệ thống dẫn đường tự động này, người ta đã ngăn bớt 1 số tuyến phố, chỉ đảm bảo sao cho giữa 2 khu phong tỏa chỉ có 1 đường đi duy nhất tới nhau. Tại mỗi điểm phong tỏa, sẽ đặt 1 máy hướng dẫn. Tại khu phong tỏa \(s\), các y bác sĩ chỉ cần nhập vào số nguyên \(d\) là khu mình cần tới, máy sẽ hiển thị số nguyên \(t\) là khu trực tiếp nối với \(s\) và là khu tiếp theo mà các y bác sĩ phải di chuyển tới. Ví dụ với hình bên, tại khu số 5, nếu các y bác sĩ cần đến khu số 4 thì máy sẽ chỉ là cần di chuyển đến khu số 3.

Cho \(n\) là số khu phong tỏa và đường đi nối trực tiếp 2 khu là cặp số \(a_{i},\ b_{i}\), cho biết có đường đi nối trực tiếp hai khu \(a_{i}\) và \(b_{i}\) \((1 \leq a_{i},\ b_{i} \leq n;\ a_{i}
eq b_{i};\ i = \ 1..n)\) và \(m\) truy vấn, mỗi truy vấn là một cặp số \(s\) và \(d\), trong đó s là khu nơi y bác sĩ đang đứng, \(d\) nơi y bác sĩ muốn đến.

Yêu cầu: Hãy xác định số hiển thị trên màn hình ứng với mỗi truy vấn.

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên \(n\ (2\ \leq \ n\ \leq \ 10^{5})\)

+ \(n - 1\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(a_{i}\) và \(b_{i}\ \)

+ Dòng kế tiếp chứa số nguyên \(m\ (1\ \leq \ m\ \leq \ 10^{5})\)

+ \(m\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(s_{j}\) và \(d_{j}\) \((1 \leq \ s_{j},\ d_{j}\ \leq n,\ s_{j}\
eq \ d_{j})\).

Kết quả:

+ Ghi \(m\) số, mỗi số \(t\) nằm trên một dòng tương ứng với kết quả của các lần tra cứu.

Ví dụ:

Ràng buộc:

+ Subtask #1: 30% số test của bài tương ứng \(n\ \leq \ 50\).

+ Subtask #2: 40% số test khác của bài tương ứng \(n\ \leq \ 100\).

+ Subtask #3: 30% số test còn lại có ràng buộc của đề bài.