#ifndef SKY
#include "island.h"
#endif // SKY
#include <bits/stdc++.h>
using namespace std;
const int N=300;
#ifdef SKY
int n;
vector<int> adj[N+1];
int d[301][301];
int vis[N+1];
int tme=0;
int now;
void dfs(int u)
{
for(int v : adj[u])
{
if(vis[v]==tme) continue;
vis[v]=tme;
d[now][v]=d[now][u]+1;
dfs(v);
}
}
int cntq=0;
int query(int v, int k)
{
cntq++;
vector<pair<int,int>> x;
for(int i=1;i<=n;++i)
{
if(i==v) continue;
x.push_back({d[v][i]*N+i,i});
}
sort(x.begin(), x.end());
return x[k-1].second;
}
void answer(int x, int y)
{
cout << x << " " << y << '\n';
}
#endif // SKY
bool got[N+1];
int dem=0;
int query(int v, int k);
void answer(int x, int y);
void solve(int n ,int t)
{
got[1]=true;
int x = query(1,1);
answer(1,x);
got[x]=1;
dem=1;
int cal=2;
while(dem<n-1)
{
int x = query(1,cal);
cal++;
if(got[x]) continue;
int c=1;
while(true)
{
int y = query(x,c);
c++;
if(got[y])
{
got[x]=1;
answer(x,y);
dem++;
break;
}
else
{
answer(x,y);
dem++;
got[y]=1;
}
}
}
}
#ifdef SKY
int main()
{
cout << "running on machine \n";
cin >> n;
int u,v;
for(int i=1;i<n;++i)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=1;i<=n;++i)
{
tme++;
now=i;
vis[i]=tme;
dfs(i);
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
cout << d[i][j] << " ";
}
cout << '\n';
}
cout << '\n';
solve(n,n*2);
cout << cntq << '\n';
}
#endif // SKY
