e-olymp
Competitions

ADA University - February 12 - LCA

LCA offline (Easy)

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

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

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

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

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

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

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

Time limit 1 second
Memory limit 122.17 MiB
Input example #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
Output example #1
1
1
1
2
5