Cho một đồ thị cây có ~N~ đỉnh ~N-1~ cạnh, có gốc là đỉnh ~1~. và ~M~ truy vấn. Mỗi truy vấn thuộc một trong hai loại sau:

1. ~root~: Chọn ~root~ làm gốc của cây
2. ~u~ ~v~: Yêu cầu tìm cha chung gần nhất của hai đỉnh ~u~ và ~v~.

Hãy lập trình và đưa ra câu trả lời ứng với các truy vấn loại ~2~.

Input

Gồm nhiều bộ test:

• Dòng ~1~: Số nguyên ~N~, số đỉnh của cây ~(1 \leq N \leq 10^{5})~.
• ~N-1~ dòng tiếp theo: Mỗi dòng gồm hai số nguyên ~u~ và ~v~ là hai đỉnh của đồ thị.
• Dòng tiếp theo: Số nguyên ~M~, số truy vấn ~(1 \leq M \leq 10^{5})~.
• ~M~ dòng tiếp theo, mỗi dòng thuộc một trong hai loại truy vấn đã cho: "! ~root~" ứng với truy vấn loại ~1~ và "? ~u~ ~v~" ứng với truy vấn loại ~2~.
• Kết thúc bộ test là số ~0~.

Output

Đưa ra các câu trả lời ứng với các bộ, mỗi câu trả lời in ra trên một dòng.

Sample Input

9
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
5
? 4 5
? 5 6
? 8 7
! 6
? 8 7
0

Sample Output

2
1
3
6