Xenia — một lập trình viên, có một cái cây gồm ~n~ đỉnh. Các đỉnh được đánh số từ ~1~ tới ~n~ và có màu xanh hoặc đỏ. Ban đầu, đỉnh ~1~ được tô màu đỏ, trong khi các đỉnh còn lại được tô màu xanh.
Khoảng cách giữa hai đỉnh ~u~ và ~v~ được định nghĩa là số cạnh trên đường đi ngắn nhất từ ~u~ tới ~v~.
Xenia có các truy vấn thuộc ~1~ trong ~2~ loại sau:
~1\ i~: tô đỉnh ~i~ từ màu xanh thành màu đỏ.
~2\ i~: In khoảng cách ngắn nhất từ đỉnh ~i~ tới một đỉnh đang có màu đỏ (nếu đỉnh ~i~ đang được tô màu đỏ thì đáp án sẽ là ~0~).
Vì Xenia không thể giải được bài toán trên nên bạn hãy giúp anh ấy giải bài toán này nhé!
Input
Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ (~2 \leq n \leq 10^5~, ~1 \leq m \leq 10^5~), lần lượt là số đỉnh của cây và số truy vấn của bài toán.
Mỗi dòng trong số ~n - 1~ dòng tiếp theo chứa hai số nguyên dương ~a_i~ và ~b_i~ (~1 \leq a_i, b_i, \leq n~, ~a_i \neq b_i~) thể hiện một cạnh của cây.
Mỗi dòng trong số ~m~ dòng tiếp theo gồm 2 số có dạng ~1\ i~ hoặc ~2\ i~ (~1 \leq i \leq n~) thể hiện một truy vấn thuộc ~2~ loại truy vấn ở trên.
Dữ liệu đảm bảo lúc thực hiện truy vấn ~1~ thì đỉnh ~i~ đang có màu xanh.
Output
Với mỗi truy vấn thuộc loại ~2~ thì in ra câu trả lời cho truy vấn đó.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
~1~ | ~20~ | ~n, q \leq 5000~ |
~2~ | ~30~ | Mọi truy vấn ~1~ diễn ra trước truy vấn ~2~ |
~3~ | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
3 3
1 2
2 3
2 3
1 2
2 3
Sample Output 1
2
1
Sample Input 2
5 4
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5
Sample Output 2
0
3
2
Notes
Ở test ví dụ đầu tiên:
Trong truy vấn loại ~2~ đầu tiên, đỉnh màu đỏ gần với đỉnh ~3~ nhất là đỉnh ~1~ nên khoảng cách tới đỉnh màu đỏ gần nhất là ~d(3, 1) = 2~.
Trong truy vấn loại ~2~ tiếp theo, đỉnh màu đỏ gần với đỉnh ~3~ nhất là đỉnh ~2~ nên khoảng cách tới đỉnh màu đỏ gần nhất là ~d(3, 2) = 1~.
Ở test ví dụ thứ hai:
Trong truy vấn loại ~2~ đầu tiên, đỉnh ~1~ đã được tô màu đỏ nên khoảng cách của đỉnh này tới đỉnh màu đỏ gần nhất là ~d(1, 1) = 0~.
Trong truy vấn loại ~2~ tiếp theo, đỉnh màu đỏ gần với đỉnh ~5~ nhất là đỉnh ~1~ nên khoảng cách tới đỉnh màu đỏ gần nhất là ~d(5, 1) = 3~.
Trong truy vấn loại ~2~ cuối cùng, đỉnh màu đỏ gần với đỉnh ~5~ nhất là đỉnh ~2~ nên khoảng cách tới đỉnh màu đỏ gần nhất là ~d(5, 2) = 2~.
Comments