Məsələlər
LCA offline (Easy)
LCA offline (Easy)
Изначально имеется дерево, состоящее только из корня (вершина с номером $1$). Требуется научиться отвечать на следующие запросы:
\begin{itemize}
\item \textbf{ADD} $~a~b$ --- подвесить вершину $b$ за вершину $a$ (гарантируется, что вершина $a$ уже существует).
\item \textbf{GET} $~a~b$ --- вернуть \textbf{LCA} вершин $a$ и $b$.
\end{itemize}
Вершины имеют номера от $1$ до $n$. В каждый момент времени у нас имеется одно дерево.
\InputFile
В первой строке содержится количество запросов $k$. Следующие $k$ строк содержат сами запросы. Гарантируется, что число запросов каждого из типов не превосходит $1000$.
\OutputFile
Для каждого запроса типа \textbf{GET} выведите в отдельную строку одно целое число --- ответ на соответствующий запрос.
\includegraphics{https://static.e-olymp.com/content/88/880951afafc2d4d42595b20022206371341a71e8.gif}
Giriş verilənləri #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
Çıxış verilənləri #1
1 1 1 2 5