Truy vấn trên cây lần nữa (Query on a tree again!)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Ban đầu mọi đỉnh đều trắng. Phép cập nhật đổi màu một đỉnh. Truy vấn yêu cầu tìm đỉnh đen đầu tiên trên đường đi từ gốc 1 đến đỉnh $v$, hoặc -1 nếu không có.

Dữ liệu vào

Dòng đầu chứa $n,q$, tiếp theo $n-1$ cạnh. Sau đó là $q$ lệnh 0 i hoặc 1 v.

Kết quả

Với mỗi lệnh loại 1, in đỉnh đen đầu tiên từ gốc đến $v$, hoặc -1.

Subtask

Subtask 1 (20%)

• Kích thước cây và số thao tác không vượt 20.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• Kích thước cây và số thao tác không vượt 2000.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n\le10^5$; số truy vấn theo định dạng của bài.

Ví dụ

Input

1 13
0 1
1 1
0 1
1 1
0 1
1 1
1 1
0 1
1 1
1 1
1 1
1 1
0 1

Output

1
-1
1
1
-1
-1
-1
-1

Giải thích

Ví dụ được xử lý đúng theo thứ tự các thao tác. Các truy vấn chỉ quan sát trạng thái hiện tại sau toàn bộ cập nhật đứng trước chúng; kết quả in ra tương ứng với định nghĩa ở phần Đề bài.