Để tránh cho khách du lịch khỏi đi lòng vòng trong một khu vực nào đó, ở một số hang người ta ngăn bớt lối ra, đảm bảo sao cho giữa 2 hang bất kỳ luôn có một đường đi duy nhất nối tới nhau. Ngoài ra, ở mỗi hang đều có đặt máy hướng dẫn. Ở tại hang 𝑠, khách chỉ cần nhập vào số nguyên 𝑑 là hang mình muốn tới, máy sẽ hiển thị số nguyên 𝑡 là hang trực tiếp nối với 𝑠 và là nơi tiếp theo khách phải di chuyển tới. Ví dụ, với sơ đồ hang ở hình bên, tại hang số 5 nếu khách nhập vào số 4 là hang muốn tới, thì máy hiển thị số 3 là hang cần đi tới và tiếp tục tra cứu dần dần khách sẽ tới được nơi mình muốn đến.

Số lượng hang trong hệ thống hang động là 𝑛, các hang được đánh số từ 1 đến 𝑛, có 𝑛 − 1 đường đi hai chiều nối trực tiếp giữa hai hang. Có tất cả 𝑚 truy vấn, mỗi truy vấn là một cặp số 𝑠 và 𝑑, trong đó 𝑠 là hang khách đang đứng, 𝑑 là hang khách muốn đến. Hãy xác định số hiển thị trên màn hình ứng với mỗi truy vấn.

Input:

o Dòng đầu tiên chứa một số nguyên 𝑛.

o Dòng thứ 𝑖 trong 𝑛 − 1 dòng tiếp theo chứa hai số nguyên 𝑎𝑖 và 𝑏𝑖 là đường đi hai chiều trực tiếp nối hai hang 𝑎𝑖 và 𝑏𝑖, (1 ≤ 𝑎𝑖, 𝑏𝑖 ≤ 𝑛; 𝑎𝑖 ≠ 𝑏𝑖).

o Dòng tiếp theo chứa số nguyên 𝑚.

o Dòng thứ 𝑗 trong 𝑚 dòng tiếp theo chứa hai số nguyên 𝑠𝑗 và 𝑑𝑗, (1 ≤ 𝑠𝑗, 𝑑𝑗 ≤ 𝑛; 𝑠𝑗 ≠ 𝑑𝑗).

Output:

o 𝑚 số nguyên, mỗi số ghi trên một dòng là kết quả của các lần tra cứu.

Giới hạn

o 2 ≤ 𝑛 ≤ 2 × 100000

o 1 ≤ 𝑚 ≤ 100000

Sample Input

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

Sample Output

3 
4 
1