Trụ sở của VNOI mới đây đã được xây dựng lại vô cùng hiện đại và hoành tráng. Do được quản lý bởi các nhà lập trình viên tài năng trên khắp đất nước Việt Nam, cấu trúc của trụ sở mới này cũng được thiết kế vô cùng đặc biệt. Tòa nhà có ~n~ căn phòng được đánh số lần lượt từ ~1~ đến ~n~. Các căn phòng được kết nối với nhau bởi ~n - 1~ hành lang đảm bảo rằng từ một căn phòng có thể đi đến bất cứ căn phòng nào khác trong tòa nhà. Ở tòa nhà này, ban đầu sẽ chỉ có căn phòng ~1~ được bật đèn và trong ~n - 1~ căn phòng còn lại đèn sẽ tắt. Thời gian tới, tòa nhà sẽ chào đón thêm các nhân viên chuyển đến nên sẽ phải bật thêm đèn ở một số căn phòng, những lần như vậy ban quản lý tòa nhà sẽ thông báo bật điện tại một căn phòng nào đó. Là một nhân viên mới ở VNOI, mỗi lần làm việc, bạn phải tiếp đón một khách hàng tại căn phòng được chỉ định sẵn và bạn sẽ phải tìm độ dài đường đi ngắn nhất từ từ căn phòng được chỉ định ấy đến một căn phòng được bật sáng gần nhất để có thể chuẩn bị cho buổi làm việc của mình.

Input

Dòng đầu tiên chứa số ~n~ và ~m~ cho biết số phòng của tòa nhà và tổng số lần bật đèn ở các căn phòng cũng như số lần mà bạn phải làm việc với khách hàng. ~(1 \leq n,m \leq 10^5)~

~n - 1~ dòng tiếp theo mỗi dòng chứa 2 số ~u~ ~v~ thể hiện có một hành lang kết nối giữa phòng ~u~ và phòng ~v~ ~(1 \leq u,v \leq n)~

~m~ dòng cuối mỗi dòng chứa ~1~ cặp số ~(t,u)~ cho biết ~2~ loại truy vấn:

- ~1~ ~u~ : Bật đèn ở phòng ~u~.

- ~2~ ~u~ : Cho biết độ dài đường đi ngắn nhất từ một căn phòng đang được bật sáng tới phòng ~u~.

Dữ liệu đảm bảo các truy vấn đều đúng với mô tả đề bài.

Output

Gồm một số dòng mỗi dòng là câu trả lời cho truy vấn loại ~2~

Scoring

Scoring table:

Sample Input 1

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

Sample Output 1

0
3
2