Tín Hiệu Đỏ Gần Nhất

Có $n$ trạm được nối bởi $n-1$ đường truyền, tạo thành một cây vô hướng. Các trạm được đánh số từ $1$ đến $n$. Ban đầu chỉ trạm $1$ phát tín hiệu đỏ; mọi trạm khác có màu xanh.

Khoảng cách giữa hai trạm là số cạnh trên đường đi đơn duy nhất nối chúng. Hệ thống thực hiện $m$ thao tác theo thứ tự:

• $1$ $v$: đổi trạm $v$ từ xanh thành đỏ. Trạm đã đỏ sẽ giữ màu đỏ đến hết quá trình.
• $2$ $v$: tìm khoảng cách nhỏ nhất từ $v$ đến một trạm đỏ hiện tại.

Dữ liệu bảo đảm mọi thao tác loại $1$ chọn một trạm đang xanh.

Input

• Dòng đầu chứa hai số nguyên $n,m$.
• Mỗi trong $n-1$ dòng tiếp theo chứa hai số nguyên $u,v$, mô tả một cạnh của cây.
• Mỗi trong $m$ dòng cuối chứa một thao tác $t$ $v$.

Output

• Với mỗi thao tác loại $2$, in khoảng cách nhỏ nhất cần tìm trên một dòng.

Constraints

• $2\le n\le 10^5$.
• $1\le m\le 10^5$.
• $1\le u,v\le n,u\ne v$ đối với mọi cạnh.
• $n-1$ cạnh tạo thành một cây vô hướng.
• $t\in \{1,2\}$ và $1\le v\le n$ đối với mọi thao tác.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 40,m\le 100$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

3
1
2
1
0