#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> lnum;
const int MAXN = (int)1e7 + 10;

int n, l;
vector <int> g[500010];
vector <pii> q;
vector<int> tin, tout;
int timer;
vector < vector<int> > up;

void dfs (int v, int p = 0) {
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i=1; i<=l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (to != p)
            dfs (to, v);
    }
    tout[v] = ++timer;
}

bool upper (int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca (int a, int b) {
    if (upper (a, b))  return a;
    if (upper (b, a))  return b;
    for (int i=l; i>=0; --i)
        if (! upper (up[a][i], b))
            a = up[a][i];
    return up[a][0];
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        string s;
        int x, y;
        cin >> s >> x >> y;
        x--;y--;
        if (s == "ADD"){
            g[x].push_back(y);
            g[y].push_back(x);
        } else{
            q.push_back(make_pair(x, y));
        }
    }
    tin.resize (n),  tout.resize (n),  up.resize (n);
    l = 1;
    while ((1<<l) <= n)  ++l;
    for (int i=0; i<n; ++i)  up[i].resize (l+1);
    for (int i = 0; i < n; i++)
        if (g[i].size() > 0){
            dfs(i);
            break;
        }

    for (int i = 0; i < q.size(); i++) {
        int a = q[i].x, b = q[i].y; // текущий запрос
        int res = lca (a, b); // ответ на запрос
        cout << res + 1 << endl;
    }
    return 0;
}