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 ≤ n ≤ 10^5, 1 ≤ m ≤ 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 \(n - 1\) dòng tiếp theo gồm \(2\) số nguyên dương \(u\) và \(v (1 ≤ u, v ≤ n).\)

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 đó.

Sample Input

3 3
1 2
2 3
2 3
1 2
2 3

Sample Output

2
1