Có $N$ cây có gốc, mỗi cây ban đầu chỉ gồm một đỉnh. Các đỉnh được đánh số từ $1$ đến $N$.

Hãy viết chương trình thực hiện các truy vấn sau:

• 1 u v: Nối một cạnh giữa $u$ và $v$, trong đó $v$ trở thành cha của $u$. Trước khi thực hiện truy vấn, $u$ là gốc của cây chứa nó, và $u$ và $v$ thuộc hai cây khác nhau.
• 2 v: Cắt cạnh nối $v$ và cha của $v$. $v$ không phải là gốc.
• 3 u v: In ra LCA của $u$ và $v$. $u$ và $v$ nằm trong cùng một cây.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($2 \le N \le 100{,}000$) và số lượng truy vấn $M$ ($1 \le M \le 200{,}000$).

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn.

Dữ liệu ra

Đối với mỗi truy vấn loại 3, in ra kết quả trên một dòng theo thứ tự.

Ví dụ

Đầu vào mẫu 1

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

Đầu ra mẫu 1

1
2
3
2