Задача №2787. Присоединяй и властвуй

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

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

Все номера вершин от \(1\) до \(N\).

В каждый момент времени у нас есть одно дерево.

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

В первой строке входного файла содержится число \(k\) — количество запросов. Следующие \(k\) строк содержат сами запросы. Гарантируется, что число запросов каждого из типов не превосходит \(500\,000\).

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

Для каждого запроса типа GET выведите в отдельную строку одно целое число — ответ на соответствующий запрос.

Примеры
Входные данные
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
2
5
Сдать: для сдачи задач необходимо войти в систему