#include<bits/stdc++.h>
using namespace std;
const int MAXN=1024;
vector<int>v[MAXN];
vector<int>level,euler;
vector<pair<int,int> >query;
int n,logg[MAXN*2],s[MAXN][MAXN],idx[MAXN];
bool used[MAXN];
///----------------------------------------------
void read()
{
    string s;
    int x,y;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        cin>>x>>y;
        if(s=="ADD")
        {
            v[x].push_back(y);
            v[y].push_back(x);
        }
        else
        {
            query.push_back(make_pair(x,y));
        }
    }
}
///----------------------------------------------
void dfs(int i,int lvl)
{
    used[i]=true;
    level.push_back(lvl);
    euler.push_back(i);
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(!used[nb])
        {
            dfs(nb,lvl+1);
            level.push_back(lvl);
            euler.push_back(i);
        }
    }
}
///----------------------------------------------
void init_sparse()
{
    for(int i=0;i<level.size();i++)s[i][0]=i;
}
///----------------------------------------------
void init_edges()
{
    memset(used,0,sizeof(used));
    for(int i=0;i<euler.size();i++)
    {
        if(!used[euler[i]])
        {
            idx[euler[i]]=i;
            used[euler[i]]=true;
        }
    }
}
///----------------------------------------------
void init_logg()
{
    logg[1]=0;
    for(int i=2;i<=MAXN;i++)
    {
        logg[i]=logg[i-1];
        if((i&(i-1))==0)logg[i]++;
    }
}
///----------------------------------------------
void make_sparse()
{
    for(int j=1;(1<<j)<n;j++)
    {
        for(int i=0;i+(1<<j)-1<n;i++)
        {
            int z1=s[i][j-1],z2=s[i+(1<<(j-1))][j-1];
            if(level[z1]<level[z2])
                s[i][j]=z1;
            else
                s[i][j]=z2;
        }
    }
}
///----------------------------------------------
void lca(int l,int r)
{
    l=idx[l];
    r=idx[r];
    if(r<l)swap(l,r);
    cout<<l<<" "<<r<<endl;
    int x,y;
    x=r-l+1;
    y=logg[r];
    int z1,z2;
    z1=s[l][y];
    z2=s[r-(1<<y)][y];
    cout<<l<<" "<<y<<" "<<r-(1<<y)<<" "<<z1<<" "<<z2<<endl;
    if(level[z1]<level[z2])
        cout<<euler[z1]<<endl;
    else
        cout<<euler[z2]<<endl;
}
///----------------------------------------------
void solve()
{
    dfs(1,1);
    init_sparse();
    make_sparse();
    init_edges();
    init_logg();
    for(int i=0;i<level.size();i++)cout<<level[i]<<" ";
    cout<<endl;
    for(int i=0;i<euler.size();i++)cout<<euler[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++)cout<<idx[i]<<" ";
    cout<<endl;

    for(int i=0;i<query.size();i++)
    {
        cout<<query[i].first<<" "<<query[i].second<<endl;
        lca(query[i].first, query[i].second);
    }
}
///----------------------------------------------
int main ()
{
    read();
    solve();
    return 0;
}