Cho một cây có ~n~ đỉnh. Ban đầu không có cạnh nào, mỗi đỉnh là gốc của chính đỉnh đó.

Bạn cần thực hiện hai loại truy vấn sau:

~\scriptsize \bullet~ Gốc ~a~ trở thành con của gốc ~b~ (và không còn là gốc nữa),

~\scriptsize \bullet~ Cho một node ~c~, in ra khoảng cách từ ~c~ đến gốc của nó.

Với truy vấn thứ hai, nếu ~c~ là gốc thì kết quả sẽ bằng 0, ngược lại kết quả sẽ là một số nguyên dương — độ "sâu" của node đó.

Viết chương trình giải quyết các truy vấn trên.

Input

Dòng đầu chứa hai số nguyên ~n~ và ~m~ ~(1 \leq n, m \leq 3 \cdot 10^5)~ — số lượng đỉnh và số lượng truy vấn tương ứng.

~m~ dòng tiếp theo chứa các truy vấn. Truy vấn thứ nhất có dạng "~\texttt{1}~ ~a~ ~b~" ~(1 \leq a \neq b \leq n)~, trong đó ~a~ và ~b~ đều là các gốc. Truy vấn thứ hai có dạng "~\texttt{2}~ ~c~" ~(1 \leq c \leq n)~.

Output

Với mỗi truy vấn loại hai, in ra kết quả trên một dòng.

Scoring

Sample Input 1

10 20
1 9 4
1 2 6
2 10
1 10 5
2 5
1 7 4
1 8 5
2 1
1 6 5
1 3 5
1 1 4
1 5 4
2 7
2 2
2 4
2 3
2 4
2 2
2 2
2 10

Sample Output 1

0
0
0
1
3
0
2
0
3
3
2