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