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.

Input

• 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à nút ~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)~.

Output

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

Sample Input

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

Sample Output

-1
8
-1
2
-1