📘 Mô tả

Ban đầu cây chỉ có một đỉnh gốc là đỉnh số 1. Sau đó có q truy vấn. Có hai loại truy vấn:

• 1 u: thêm một đỉnh mới, đánh số tự động tiếp theo, làm con trực tiếp của đỉnh u.
• 2 u v: in ra tổ tiên chung gần nhất (LCA) của hai đỉnh u và v trong cây hiện tại.

📥 Input

• Dòng đầu tiên chứa số nguyên q (1 ≤ q ≤ 10⁵): số lượng truy vấn.
• q dòng tiếp theo, mỗi dòng là một truy vấn có dạng 1 u hoặc 2 u v như mô tả ở trên.

📤 Output

Với mỗi truy vấn loại 2, in ra một dòng chứa số nguyên duy nhất là tổ tiên chung gần nhất của u và v.

🧪 Ví dụ

Input:

6
1 1
1 1
1 2
2 2 3
2 4 3
2 4 1

Output:

1
1
1