Sladoledite

// #include <bits/stdc++.h>
// #define ll long long

// using namespace std;

// vector<vector<int>> up;
// vector<int> depth;
// vector<int> mapped;
// const int LOG = 20;

// void add(int u, int p) {
//     depth[u] = depth[p] + 1;
//     up[u][0] = p;
//     for (int l = 1; l < LOG; l++) {
//         up[u][l] = up[up[u][l-1]][l-1];
//     }
// }

// int lca(int u, int v) {
//     if (u == v) return u;
//     if (depth[u] > depth[v]) swap(u, v);
//     for (int i = depth[v] - depth[u], k = 0; i > 0; i /= 2, k++) {
//         if (i & 1) v = up[v][k];
//     }
//     if (u == v) return u;
//     for (int i = LOG - 1; i >= 0; i--) {
//         if (up[u][i] != up[v][i]) {
//             u = up[u][i];
//             v = up[v][i];
//         }
//     }
//     return up[u][0];
// }

// int main() {
//     int N;
//     cin >> N;
//     depth.resize(N + 10);
//     up.resize(N + 10, vector<int>(LOG, 0));
//     mapped.resize(N + 10);
//     for (int i = 1; i <= N; i++) {
//         char c;
//         cin >> c;
//         if (c == 'a') {
//             int u;
//             cin >> u;
//             add(i, mapped[u]);
//             mapped[i] = i;
//         } else if (c == 'b') {
//             int u;
//             cin >> u;
//             u = mapped[u];
//             int p = up[u][0];
//             cout << u << endl;
//             mapped[i] = p;
//         } else {
//             int u, v;
//             cin >> u >> v;
//             u = mapped[u];
//             v = mapped[v];
//             mapped[i] = u;
//             cout << depth[lca(u, v)] << endl;
//         }
//     }
//     return 0;
// }

#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
const int mod = 1e9 + 7;
int LOG = 0;
const int maxn = 3e5 + 5;
using namespace std;

void setUSA(string name) {
     freopen( (name + ".in").c_str(), "r", stdin);
     freopen( (name + ".out").c_str(), "w", stdout);
}

void setIO(string name = "") {
     ios_base::sync_with_stdio(false);
     cout.tie(nullptr);
     cin.tie(nullptr);
     if(name != "") setUSA(name);
}

vector<int> depth;
vector<int> cream;
vector<vector<int> > up;

void update(int node, int parent, int cnt) {
     depth[node] = depth[parent] + 1;
     up[node][0] = parent;

     for(int j=1; j<LOG; j++)
          up[node][j] = up[ up[node][j-1] ][j-1];
}

int jmp(int x, int d) {
     for(int j=LOG-1; j>=0; j--) {
          if(d & (1 << j)) {
               x = up[x][j];
               //cout << "jumped to depth: " << depth[x] << ", steps: " << pow(2, j) << '\n';
          }
     }

     return x;
}

int get_lca(int a, int b) {
     if(depth[a] < depth[b]) swap(a, b);
     //cout << "before jump: " << depth[a] << " - "<< depth[b] << '\n';
     a = jmp(a, depth[a] - depth[b]);
     //cout << "after jump: " << depth[a] << " - " << depth[b] << '\n';
     if(a == b) return a;

     for(int j=LOG - 1; j>=0; j--)
          if(up[a][j] != up[b][j])
               a = up[a][j], b = up[b][j];

     return up[a][0];
}

int main() {
    //setIO();

    int n, cnt = 1;
    cin >> n;
    while((1 << LOG) <= n) LOG++;
    LOG += 2;
    up.resize(n+1, vector<int>(LOG, 0));
    depth.resize(n+1, 0);
    cream.resize(n+1, 0);

    while(n--) {
          char ch;
          cin >> ch;

          if(ch == 'a') {
               int a;
               cin >> a;
               a = cream[a];
               update(cnt, a, cnt);
               cream[cnt] = cnt;
          } else if(ch == 'b') {
               int a;
               cin >> a;
               a = cream[a];
               cream[cnt] = up[a][0];
               cout << a << '\n';
          } else {
               int a, b;
               cin >> a >> b;
               a = cream[a];
               b = cream[b];
               cream[cnt] = a;
               int lca = get_lca(a, b);
               cout << depth[lca] << '\n';
          }

          cnt++;
    }

    return 0;
}