Xenia có một cây vô hướng gồm n đỉnh, đánh số từ 1 đến n. Ta coi đỉnh 1 được tô đỏ ngay từ đầu, các đỉnh còn lại đều xanh.

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

Xenia cần xử lý nhanh hai loại truy vấn:

1. Tô đỏ một đỉnh màu xanh được chỉ định.
2. Với một đỉnh cho trước, hãy tìm khoảng cách nhỏ nhất tới đỉnh đỏ gần nhất.

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

Dữ liệu vào (Input)

• Dòng 1: hai số nguyên n và m — số đỉnh của cây và số truy vấn (2 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5).
• n 1 dòng tiếp theo: mỗi dòng chứa hai số nguyên a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) — một cạnh của cây.

• m dòng tiếp theo: mỗi dòng chứa cặp t_i, v_i (1 ≤ t_i ≤ 2, 1 ≤ v_i ≤ n) mô tả một truy vấn:

  • Nếu t_i = 1: tô đỏ đỉnh v_i.
  • Nếu t_i = 2: in khoảng cách ngắn nhất từ v_i đến một đỉnh đỏ bất kỳ.

Bảo đảm đồ thị cho trước là một cây, và mọi truy vấn đều hợp lệ.

Kết quả (Output)

• Đối với mỗi truy vấn loại 2, in ra một dòng là kết quả tương ứng.

Ví dụ

Input

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

Output

1
0
2

Giải thích: ban đầu chỉ đỉnh 1 đỏ. Sau truy vấn 1 2, đỉnh 2 cũng đỏ.

• Truy vấn 2 1: gần nhất với đỉnh 1 là đỉnh 2 (khoảng cách 1).
• Truy vấn 2 2: chính nó đã đỏ (khoảng cách 0).
• Truy vấn 2 5: gần nhất là một trong {1,2} với khoảng cách 2.