LCA offline#5217
Initially you are given a tree consisting of only one root (the vertex with the number ). You need to answer the following queries:
ADD a b - hang the vertex under the vertex (it is guaranteed that the vertex already exists).
GET a b - return the LCA of vertices and .
The vertices are numbered from to . At each moment of time you have only one tree.
The first line contains the number of queries . Next lines contain the queries. There are no more than queries of each type.
For each query of type GET print in separate line one integer - the answer to the corresponding query.
Example 1