Cho một cây có N đỉnh, các đỉnh đánh số 1, 2, …, N. Khởi đầu, đỉnh 1 tô màu đen, tất cả các đỉnh còn lại của cây tô màu trắng. Khoảng cách giữa hai đỉnh u và v được định nghĩa là số cạnh của đường đi từ u đến v có số cạnh ít nhất. Hãy thực hiện m truy vấn thuộc một trong hai loại sau:

1. Tô lại màu của một đỉnh từ màu trắng thành màu đen.

2. Tìm một đỉnh có màu đen gần (khoảng cách nhỏ nhất) với một đỉnh u. Chỉ in ra giá trị khoảng cách này.

Input:

• Dòng 1: chứa 2 số nguyên dương N, M ( 2 ≤ N ≤ 100000, 1 ≤ M ≤ 100000)

• N – 1 dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương u, v (1 ≤ u ≠ v ≤ N) mô tả một cạnh của cây. Dữ liệu đảm bảo đồ thị liên thông.

• M dòng cuối cùng mô tả M truy vấn thực hiên lần lượt, mỗi truy vấn có một trong hai dạng:

• 1 v : Tô lại màu đỉnh v từ màu trắng thành màu đen.

• 2 v :Tìm đỉnh u có màu đen. Nếu có nhiều đỉnh như vậy, tìm đỉnh có khoảng cách đến v nhỏ nhất. Chỉ cần in ra giá trị khoảng cách này.

Output:

Với mỗi truy vấn loại 2 in ra trên một dòng một số nguyên duy nhất là kết quả tìm được.

Sample Input

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

Sample Output

0
3
2