Tý cần giải bài toán sau:

\text{Tìm đỉnh gần nhất}

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 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.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Khu rừng FPTOJ có \(N\) cây và \(N-1\) con đường. Các nhà thám hiểm muốn đánh dấu một số cây làm trạm dừng chân. Lúc đầu chưa có cây nào được đánh dấu. Có \(Q\) sự kiện xảy ra, mỗi sự kiện thuộc một trong hai loại:

• Loại 1 \(u\): Đổi trạng thái đánh dấu của cây \(u\) (nếu chưa đánh dấu thì đánh dấu, nếu đã đánh dấu thì bỏ).
• Loại 2 \(u\): Cho biết khoảng cách ngắn nhất từ cây \(u\) đến một cây đã được đánh dấu bất kỳ. Nếu không có cây nào được đánh dấu, in ra \(-1\).

Đầu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa \(u, v\).
• Dòng tiếp theo chứa \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa \(t_j, u_j\).

Đầu ra

• Với mỗi truy vấn loại 2, in ra kết quả trên một dòng.

Ví dụ

Đầu vào:

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

Đầu ra:

-1
2
1
1
3

Giải thích

Ban đầu không có đỉnh nào được đánh dấu → truy vấn đầu ra -1. Đánh dấu đỉnh 4 → khoảng cách 4→1 là 2. Đánh dấu thêm đỉnh 1 → khoảng cách 1→1 là 1.

Subtask