#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
const int MAXN = (1 << 20);
const int MAXLOG = 20;

struct dsu
{
	int sz;
	vector<int> par, psz;

	void init(int n)
	{
		sz = n;
		par.assign(sz + 1, 0);
		psz.assign(sz + 1, 0);
		for(int i = 0; i <= sz; i++)
			par[i] = i, psz[i] = 1;
	}

	int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
	
	bool connected(int x, int y) { return root(x) == root(y); }

	void unite(int x, int y)
	{
		x = root(x), y = root(y);
		if(psz[x] > psz[y]) swap(x, y);
		par[x] = y, psz[y] += psz[x]; 
	}
};

int n = 0, q;
vector<int> G[MAXN];
string type[MAXN];
int argg[MAXN];

void read()
{
	cin >> q;
	for(int i = 0; i < q; i++)
	{
		cin >> type[i] >> argg[i];
		if(type[i] == "B")
		{
			n++;
			if(argg[i] != -1) 
			{
				G[argg[i]].push_back(n);
				G[n].push_back(argg[i]);
			}
		}
	}
}

int dep[MAXN], st[MAXN], en[MAXN], dfs_time = 0;
int par[MAXN][MAXLOG];

void dfs_lca(int u)
{
	st[u] = ++dfs_time;
	for(int i = 1; i < MAXLOG; i++)
		par[u][i] = par[par[u][i - 1]][i - 1];

	for(int v: G[u])
		if(v != par[u][0])
		{
			par[v][0] = u;
			dep[v] = dep[u] + 1;
			dfs_lca(v);
		}

	en[u] = dfs_time;
}

inline bool upper(int u, int v) { return st[u] <= st[v] && en[v] <= en[u]; }

int lca(int u, int v)
{
	if(upper(u, v)) return u;
	if(upper(v, u)) return v;

	int a = u;
	for(int i = MAXLOG - 1; i >= 0; i--)
		if(!upper(par[a][i], v))
			a = par[a][i];

	return par[a][0];
}

int parent(int u, int up)
{
	int a = u;
	for(int i = MAXLOG - 1; i >= 0; i--)
		if(up & (1 << i))
			a = par[a][i];

	return a;
}

void lca_precompute(int root)
{
	for(int i = 0; i < MAXLOG; i++)
        par[root][i] = root;

	dfs_time = 0;
	dfs_lca(root);
}

bool used[MAXN];
dsu d;

void dfs_check(int u)
{
	used[u] = 1;
	for(int v: G[u])
		if(!used[v])
			dfs_check(v);
}

int d1[MAXN], d2[MAXN];
int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }

void merge(int a, int b)
{
	d.unite(a, b);

	vector<int> cands = {d1[a], d2[a], d1[b], d2[b]};
	int root = d.root(a);

	int mx = 0;
	for(int i = 0; i < (int)cands.size(); i++)
		for(int j = i + 1; j < (int)cands.size(); j++)
		{
			int d = dist(cands[i], cands[j]);
			if(d > mx)
			{
				mx = d;
				d1[root] = cands[i];
				d2[root] = cands[j];
			}
		}
}

void solve()
{
	for(int i = 1; i <= n; i++)
		if(!used[i])
		{
			lca_precompute(i);
			dfs_check(i);
		}

	d.init(n);
	for(int i = 1; i <= n; i++)
		d1[i] = i, d2[i] = i;

	int c_ver = 0;
	for(int i = 0; i < q; i++)
	{
		if(type[i] == "B")
		{
			c_ver++;
			if(argg[i] != -1)
				merge(d.root(argg[i]), d.root(c_ver));
		}
		else
		{
			int u = argg[i], c = d.root(u);
			cout << max(dist(u, d1[c]), dist(u, d2[c])) << endl;
		}
	}
}

int main()
{
	freopen("newbarn.in", "r", stdin);
	freopen("newbarn.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	read();
	solve();
	return 0;
}