#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

const int MXN = 1e5 + 5, INF = 1e9 + 5;
int N, Q, node;
vector<pair<char, int>> queries;
vector<int> g[MXN];
vector<pair<int, int>> par[MXN];
int subtree[MXN];
bool vis[MXN];

struct two_set {
    pair<int, int> x = {-INF, -1}, y = {-INF, -1};

    void insert(int dist, int id) {
        pair<int, int> z = make_pair(dist, id);

        if (x.second == id) x = max(y, z);
        else  y = max(y, z);

        if (x.first < y.first) swap(x, y);
    }

    int query(int id) {
        return (x.second == id ? y.first : x.first);
    }
};

two_set best[MXN];

void calc_subtree(int u, int p) {
    subtree[u] = 1;

    for (const auto &v : g[u]) {
        if (v == p) continue;
        calc_subtree(v, u);
        subtree[u] += subtree[v];
    }
}

int find_centroid(int u, int p, int vertices) {
    if (p != -1) {
        subtree[p] -= subtree[u];
        subtree[u] += subtree[p];
    }

    for (const auto &v : g[u]) {
        if (v == p || vis[v]) continue;

        if (subtree[v] * 2 > vertices)
            return find_centroid(v, u, vertices);
    }

    return u;
}

void dfs(int u, int p, int dist, int centroid) {
    par[u].emplace_back(centroid, dist);

    for (const auto &v : g[u]) {
        if (v == p || vis[v]) continue;
        dfs(v, u, dist + 1, centroid);
    }
}

void build_tree(int u) {
    int centroid = find_centroid(u, -1, subtree[u]);
    vis[centroid] = true;

    for (const auto &v : g[centroid]) {
        if (vis[v]) continue;
        dfs(v, centroid, 1, centroid);
    }

    for (const auto &v : g[centroid]) {
        if (vis[v]) continue;
        build_tree(v);
    }
}

void add_node(int v) {
    best[v].insert(0, v);

    int child = v;
    for (const auto &[centroid, dist] : par[v]) {
        best[centroid].insert(dist, child);
        child = centroid;
    }
}

int query(int v) {
    int ans = best[v].x.first, child = v;

    for (const auto &[centroid, dist] : par[v]) {
        ans = max(ans, dist + best[centroid].query(child));
        child = centroid;
    }

    return ans;
}

void solve() {
    cin >> Q;

    for (int i = 0; i < Q; i++) {
        char type;
        int x;
        cin >> type >> x;
        x--;

        queries.emplace_back(type, x);

        if (type == 'B') {
            if (x < 0) {
                N++;
                continue;
            }

            g[N].push_back(x);
            g[x].push_back(N);

            N++;
        }
    }

    for (int i = 0; i < N; i++) {
        if (vis[i]) continue;

        calc_subtree(i, -1);
        build_tree(i);
    }

    for (int i = 0; i < N; i++)
        reverse(all(par[i]));

    vector<bool> built(N, false);

    for (const auto &[type, v] : queries) {
        if (type == 'B') {
            if (v < 0) {
                node++;
                continue;
            }

            if (!built[v]) {
                add_node(v);
                built[v] = true;
            }

            add_node(node);
            built[node++] = true;
        } else {
            cout << (built[v] ? max(0, query(v)) : 0) << "\n";
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

#ifndef local
    freopen("newbarn.in", "r", stdin);
    freopen("newbarn.out", "w", stdout);
#endif

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}