$N$ đỉnh tạo thành một cây (đồ thị liên thông, không chu trình vô hướng). Các đỉnh được đánh số từ $1$ đến $N$, các cạnh được đánh số từ $1$ đến $N-1$. Ban đầu, tất cả các đỉnh có màu trắng.

Hãy viết chương trình thực hiện hai loại truy vấn sau:

• 1 i: Đổi màu của đỉnh thứ $i$ (trắng -> đen, đen -> trắng).
• 2 v: In ra số hiệu của đỉnh đen đầu tiên trên đường đi từ đỉnh $1$ đến đỉnh $v$. Nếu không có đỉnh nào như vậy, in ra $-1$.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($2 \le N \le 100\,000$).

$N-1$ dòng tiếp theo, dòng thứ $i$ chứa hai số $u$ và $v$ là hai đầu mút của cạnh thứ $i$.

Dòng tiếp theo chứa số lượng truy vấn $M$ ($1 \le M \le 100\,000$).

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn.

Dữ liệu ra

Với mỗi truy vấn loại $2$, in ra kết quả trên một dòng theo đúng thứ tự.

Ví dụ

Đầu vào

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

Đầu ra

-1
8
-1
2
-1