Có một cây (đồ thị liên thông không chu trình vô hướng) gồm $N$ đỉnh. 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 đen.

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 $i$ (trắng $\to$ đen, đen $\to$ trắng).
• 2 v: In ra khoảng cách ngắn nhất giữa $v$ và một đỉnh trắng $u$ bất kỳ. $u$ và $v$ có thể trùng nhau. Nếu $v$ là màu trắng thì kết quả là $0$. Nếu cây không có đỉnh trắng nào thì 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ố nguyên $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

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

Đầu ra

2
2
2
3
0