eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

LCA offline (Easy)

LCA offline (Easy)

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Изначально имеется дерево, состоящее только из корня (вершина с номером 1). Требуется научиться отвечать на следующие запросы:

  • ADD~a~b — подвесить вершину b за вершину a (гарантируется, что вершина a уже существует).

  • GET~a~b — вернуть LCA вершин a и b.

Вершины имеют номера от 1 до n. В каждый момент времени у нас имеется одно дерево.

Входные данные

В первой строке содержится количество запросов k. Следующие k строк содержат сами запросы. Гарантируется, что число запросов каждого из типов не превосходит 1000.

Выходные данные

Для каждого запроса типа 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