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

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~.