Cho một đồ thị dạng cây gồm ~N~ nút được đánh số từ ~1~ đến ~N~. Gốc của cây nằm ở nút ~1~. Ban đầu, tất cả các nút trên cây đều có màu Trắng.

Có ~M~ truy vấn thuộc hai loại:

• Loại ~1~ ~(1\ v)~: Tìm nút màu Đỏ có độ sâu nhỏ nhất (gần nút gốc nhất) nằm trên đường đi đơn từ nút gốc ~1~ đến nút ~v~. Nếu trên đường đi này không có nút màu Đỏ nào, in ra ~-1~.

• Loại ~2~ ~(2\ v)~: Đảo trạng thái màu của nút ~v~. Nếu nút ~v~ đang màu Trắng sẽ trở thành màu Đỏ, và ngược lại (tuy nhiên, dựa trên logic a[id]=abs(a[id]-v) và cách cập nhật của bạn, truy vấn này thường được hiểu là đánh dấu nút ~v~ trở thành màu Đỏ).

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ ~(1 \le N, M \le 2 \times 10^5)~.

• ~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ mô tả một cạnh của cây.

• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~type~ và ~v~ mô tả loại truy vấn và nút thực hiện truy vấn.

Output

Với mỗi truy vấn loại ~1~, in ra chỉ số của nút thỏa mãn yêu cầu hoặc ~-1~ nếu không tìm thấy.

Scoring

Sample Input 1

5 4
1 2
1 3
3 4
3 5
2 3
1 4
2 1
1 5

Sample Output 1

3
1