Cho một cây con có N đỉnh, các đỉnh đánh số 1, 2, …, N. Mỗi đỉnh có một trong hai màu đen hoặc trắng. Khởi đầu, tất cả các đỉnh được tô màu đen. Khoảng cách giữa hai đỉnh u và v được định nghĩa là đường đi từ u đến v có số cạnh ít nhất.

Hãy thực hiện Q truy vấn thuộc một trong hai loại sau:

• 1 i : Đổi màu đỉnh i (từ màu đen thành màu trắng và ngược lại)

• 2 v: Tìm một đỉnh u có màu trắng (u có thể trùng với v) gần đỉnh v nhất.

Input:

• Dòng 1: chứa số nguyên dương N ( 2 ≤ N ≤ 100000)

• N – 1 dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương u, v (1 ≤ u ≠ v ≤ N) mô tả một cạnh của cây. Dữ liệu đảm bảo đồ thị liên thông.

• Dòng tiếp theo chứa số nguyên dương Q ( Q ≤ 100000)

• Q dòng cuối cùng mô tả Q truy vấn thực hiên lần lượt, mỗi truy vấn có một trong hai dạng 1 i hoặc 2 v mô tả như trên.

Output:

Với mỗi truy vấn loại 2 in ra trên một dòng một số nguyên duy nhất là khoảng cách gần nhất tìm được. Nếu tất cả các đỉnh là màu đen thì in ra -1.

Sample Input

10
1 2
1 3
2 4
1 5
1 6
4 7
7 8
5 9
1 1
10
1 6
1 6
1 6
2 3
2 10
2 4
2 6

Sample Output

2
2
2
3
0