Khoảng cách ngắn nhất

Rin có một cây gồm \(n\) đỉnh. Các đỉnh của cây được đánh số từ \(1\) đến \(n\). Ban đầu tất cả các đỉnh được sơn màu xanh.

Khoảng cách giữa hai đỉnh \(u\) và \(v\) trên cây là số cạnh trên đường đi ngắn nhất giữa \(u\) và \(v\).

Rin muốn thực hiện nhanh chóng các truy vấn thuộc hai loại sau:

• Đổi màu một đỉnh của cây, nếu đỉnh đang được sơn màu xanh thì ta sơn lại nó bằng màu đỏ và ngược lại;

• Tính xem nút màu đỏ nào gần nút nhất đã cho và in ra khoảng cách ngắn nhất đến nút màu đỏ gần nhất.

Nhiệm vụ của bạn là viết một chương trình để giúp Rin thực hiện các truy vấn trên.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((2 \leq n \leq 10^5, 1 \leq m \leq 10^5)\) - số nút trong cây và số truy vấn.

• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n, u \neq v)\) thể hiện một cạnh của cây..

• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(t\) \((1 \leq t \leq 2)\) và \(v\) \((1 \leq v \leq n)\) thể hiện \(1\) truy vấn. Nếu \(t = 1\), nếu đỉnh \(v\) được sơn màu xanh thì ta sơn lại nó bằng màu đỏ và ngược lại . Nếu \(t = 2\), in ra khoảng cách ngắn nhất từ đỉnh \(v\) đến một đỉnh được sơn màu đỏ, nếu không có đỉnh nào được sơn màu đỏ thì câu trả lời là \(-1\).

Output

Đối với mỗi truy vấn có \(t = 2\), bạn hãy in ra đáp án của truy vấn trên \(1\) dòng duy nhất.

Example

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

0
3
2
-1

Scoring

• Subtask 1 (18 điểm) : \(1 \leq n, q \leq 5000\)

• Subtask 2 (32 điểm): Số đỉnh được sơn màu đỏ tại mỗi thời điểm không quá \(500\)

• Subtask 3 (50 điểm): Không có rằng buộc gì thêm