#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,n2,d[N];
vector<int>e[N],r(N,0),s(N,0);
array<int,2>pv={-1,-1};
void rmv(int i,int j){
if(d[i]==1&&n2){
cout<<i<<endl;
r[i]=true,n2--;
d[i]--,d[j]--;
}
}
void solve1(){
cin>>n,n2=n-1;
for(int i=1,x,y;i<=n-1;i++)cin>>x>>y,e[x].push_back(y),e[y].push_back(x),d[x]++,d[y]++;
vector<array<int,2>>vl,vg;
queue<int> q;
for(int i=0;i<n;i++)if(e[i].size()==1&&!s[e[i][0]]){
s[e[i][0]]=true;
if(i<e[i][0])vl.push_back({i,e[i][0]});
else vg.push_back({e[i][0],i});
}
sort(begin(vl),end(vl)),sort(begin(vg),end(vg));
// print data
bool lg=(vl.empty()||vl.back()>vg.back());
cout<<lg<<endl;
reverse(begin(vl),end(vl)),reverse(begin(vg),end(vg));
for(auto vi:(lg?vg:vl))if(!r[vi[0]]&&n2){
if(lg)swap(vi[0],vi[1]);
rmv(vi[0],vi[1]);
for(auto i2:e[vi[1]])rmv(i2,vi[1]);
}
for(auto vi:(lg?vl:vg))if(!r[vi[0]]&&n2){
if(!lg)swap(vi[0],vi[1]);
rmv(vi[0],vi[1]);
for(auto i2:e[vi[1]])rmv(i2,vi[1]);
}
for(int i=0;i<n;i++)if(d[i]==1)q.push(i);
while(n2){
int i=q.front(); q.pop();
if(r[i])break;
int pi=-1;
for(int i2:e[i])if(d[i2])pi=i2;
rmv(i,pi);
for(int i2:e[pi])rmv(i2,pi);
q.push(pi);
}
}
void solve2(){
char c;
cin>>n>>c;
bool lg=c=='1';
for(int i=1,x,y;i<=n-1;i++){
cin>>x>>y;
// first
if(pv[0]==-1){
pv={x,y};
cout<<(lg?y:x)<<endl; // switch this to test which one
}else if(r[x]==i-1||r[y]==i-1){
if(r[x]==i-1)cout<<y<<endl;
else cout<<x<<endl;
}else if(r[x]&&r[y]) cout<<x<<endl;
else if(r[x]) cout<<x<<endl;
else if(r[y]) cout<<y<<endl;
else{
if(x>pv[0]||(x==pv[0]&&y>pv[1]))lg=!lg;
pv={x,y};
cout<<(lg?y:x)<<endl;
}
r[x]=i,r[y]=i;
}
}
main(){
int t;
cin >> t;
if(t==1)solve1();
else solve2();
}
// 1
// 3 5 2 4 1 6
