Спочатку є дерево, яке містить лише корінь (вершина з номером 1). Потрібно навчитись відповідати на наступні запити:
ADD a b - підвісити вершину b за вершину a (гарантується, що вершина a вже існує).
GET a b - повернути LCA вершин a та b.
Усі номери вершин від 1 до n. У кожен момент часу у нас є одне дерево.
У першому рядку міститься кількість запитів k. Наступні k рядків містять самі запити. Гарантується, що кількість запитів кожного типу не перевищує 500000.
Для кожного запиту типу GET виведіть в окремий рядок одне ціле число - відповідь на відповідний запит.