#include <bits/stdc++.h>
#ifndef cpismylifeOwO
#include "fun.h"
#endif // cpismylifeOwO
using namespace std;
const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;
const int MaxLog = 20;
#ifdef cpismylifeOwO
int ni;
vector<int> graph[MaxN];
void Inp()
{
cin >> ni;
for (int x = 1; x < ni; x++)
{
int u, v;
cin >> u >> v;
u++;
v++;
graph[u].push_back(v);
graph[v].push_back(u);
}
}
int par[MaxN];
int h[MaxN];
int sz[MaxN];
void PreDFS(int u, int p)
{
sz[u] = 1;
for (int x : graph[u])
{
if (x != p)
{
par[x] = u;
h[x] = h[u] + 1;
PreDFS(x, u);
sz[u] += sz[x];
}
}
}
int BinLift[MaxLog][MaxN];
void Build()
{
for (int x = 1; x <= ni; x++)
{
BinLift[0][x] = par[x];
}
for (int x = 1; x < MaxLog; x++)
{
for (int y = 1; y <= ni; y++)
{
BinLift[x][y] = BinLift[x - 1][BinLift[x - 1][y]];
}
}
}
int LCA(int u, int v)
{
if (h[u] != h[v])
{
if (h[u] > h[v])
{
swap(u, v);
}
int k = h[v] - h[u];
for (int x = 0; x < MaxLog; x++)
{
if (k & (1 << x))
{
v = BinLift[x][v];
}
}
}
if (u == v)
{
return v;
}
for (int x = MaxLog - 1; x >= 0; x--)
{
if (BinLift[x][u] != BinLift[x][v])
{
u = BinLift[x][u];
v = BinLift[x][v];
}
}
return par[u];
}
int hoursRequired(int u, int v)
{
cout << "a ";
u++;
v++;
cout << u << " " << v << " ";
int lca = LCA(u, v);
cout << h[u] + h[v] - 2 * h[lca] << "\n";
return h[u] + h[v] - 2 * h[lca];
}
int attractionsBehind(int u, int v)
{
cout << "b ";
u++;
v++;
cout << u << " " << v << " ";
int lca = LCA(u, v);
if (lca == v)
{
for (int x = MaxLog - 1; x >= 0; x--)
{
if (h[u] - (1 << x) > h[v])
{
u = BinLift[x][u];
}
}
cout << ni - sz[u] << "\n";
return ni - sz[u];
}
cout << sz[v] << "\n";
return sz[v];
}
#endif // cpismylifeOwO
int dis[MaxN];
priority_queue<pair<int, int>> group[5];
vector<int> createFunTour(int n, int Q)
{
assert(Q >= 0);
pair<int, int> cur = make_pair(n, 1);
for (int x = 2; x <= n; x++)
{
int p = attractionsBehind(0, x - 1);
if (p > n / 2)
{
cur = min(cur, make_pair(p, x));
}
}
int r = cur.second;
vector<int> af;
for (int x = 1; x <= n; x++)
{
if (x != r)
{
dis[x] = hoursRequired(r - 1, x - 1);
}
if (dis[x] == 1)
{
af.push_back(x);
//cout << x << " ";
}
}
for (int x = 1; x <= n; x++)
{
if (x != r)
{
bool done = false;
for (int y = 0; y < (int)af.size() - 1; y++)
{
int v = af[y];
if (hoursRequired(v - 1, x - 1) + 1 == dis[x])
{
group[y].push(make_pair(dis[x], x));
//cout << x << " " << y << "\n";
done = true;
}
}
if (!done)
{
group[(int)af.size() - 1].push(make_pair(dis[x], x));
//cout << x << " " << (int)af.size() - 1 << "\n";
}
}
}
vector<int> res;
int curm = -1;
if ((int)af.size() == 3)
{
while (2 * max(group[0].size(), max(group[1].size(), group[2].size())) != group[0].size() + group[1].size() + group[2].size())
{
if (2 * max(group[0].size(), max(group[1].size(), group[2].size())) > group[0].size() + group[1].size() + group[2].size())
{
int p = 0;
for (int x = 0; x < 3; x++)
{
if (max(group[0].size(), max(group[1].size(), group[2].size())) == group[x].size())
{
p = x;
break;
}
}
curm = p;
res.push_back(group[p].top().second - 1);
group[p].pop();
continue;
}
pair<pair<int, int>, int> now = make_pair(make_pair(0, 0), 0);
for (int x = 0; x < 3; x++)
{
if (curm != x && !group[x].empty())
{
now = max(now, make_pair(group[x].top(), x));
//if (curm == -1) cout << group[x].top().first << " " << group[x].top().second << "\n";
}
}
curm = now.second;
group[now.second].pop();
res.push_back(now.first.second - 1);
}
if (group[1].size() > group[0].size())
{
swap(group[0], group[1]);
if (curm == 0 || curm == 1)
{
curm ^= 1;
}
}
if (group[2].size() > group[0].size())
{
swap(group[2], group[0]);
if (curm == 0 || curm == 2)
{
curm ^= 2;
}
}
if (curm > 0)
{
if (group[curm ^ 3].top().first > group[curm].top().first)
{
curm ^= 3;
res.push_back(group[curm].top().second - 1);
group[curm].pop();
}
}
while (!group[2].empty())
{
group[1].push(group[2].top());
group[2].pop();
}
if (curm == 2)
{
curm = 1;
}
}
if ((int)group[0].size() != (int)group[1].size() && res.empty())
{
if ((int)group[0].size() < (int)group[1].size())
{
swap(group[0], group[1]);
}
curm = 0;
while ((int)group[0].size() != (int)group[1].size())
{
res.push_back(group[0].top().second - 1);
group[0].pop();
}
}
while (!group[0].empty() || !group[1].empty())
{
pair<pair<int, int>, int> now = make_pair(make_pair(0, 0), 0);
for (int x = 0; x < 2; x++)
{
if (curm != x && !group[x].empty())
{
now = max(now, make_pair(group[x].top(), x));
}
}
curm = now.second;
group[now.second].pop();
res.push_back(now.first.second - 1);
}
res.push_back(r - 1);
return res;
}
#ifdef cpismylifeOwO
void Exc()
{
PreDFS(1, -1);
Build();
vector<int> res = createFunTour(ni, 4e5);
for (int x : res)
{
cout << x << " ";
}
}
int main()
{
freopen("FUN.INP", "r", stdin);
//freopen("FUN.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
//cin >> test;
for (int x = 1; x <= test; x++)
{
Inp();
Exc();
}
return 0;
}
#endif // cpismylifeOwO
