Cho một cây (đồ thị vô hướng phi chu trình) có \(N\) nút. Các nút của cây được đánh số từ \(1\) đến \(N\). Ban đầu, mỗi nút đều có màu trắng.

Bạn phải thực hiện các thao tác có dạng sau:

• "0 i": đổi màu nút thứ \(i\) (từ đen thành trắng, hoặc từ trắng thành đen)
• "1 v": tìm chỉ số của nút đen đầu tiên trên đường đi từ nút \(1\) đến nút \(v\). Nếu không tồn tại, hãy trả về \(-1\).

Dữ liệu vào

• Dòng thứ nhất gồm hai số nguyên \(N\) và \(Q\) \((1 \le N,Q \le 10^5)\)
• \(N-1\) dòng sau, mỗi dòng gồm hai số nguyên \(a,b\) mô tả một cạnh nối giữa nút \(a\) và \(b\) \((1 \le a,b \le N)\)
• \(Q\) dòng sau chứa các thao tác dạng "0 i" hoặc "1 v" \((1 \le i, v \le N)\)

Dữ liệu ra

• Với mỗi thao tác dạng "1 v", in ra một số nguyên là kết quả.

Input 1

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

Output 1

-1
8
-1
2
-1