#include <bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int MAX=1e3+5;
int P,N;
namespace part1{
vector<int> adj[MAX];
bool vis[MAX];
int dst[MAX];
int par[MAX];
queue<int> dq;
bool diam[MAX];
void out(int x){
if (!vis[x]&&N) cout<<x<<'\n',N--,vis[x]=1;
}
void solve(){
for (int i=0;i<N-1;i++){
int a,b;cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dq.push(0);
int x;
while (dq.size()){
x=dq.front();
dq.pop();
vis[x]=1;
for (auto a:adj[x]) if (!vis[a]) dq.push(a);
}
fill_n(vis,N,0);
dq.push(x);
int y;
while (dq.size()){
y=dq.front();
dq.pop();
vis[y]=1;
for (auto a:adj[y]) if (!vis[a]) par[a]=y,dst[a]=dst[y]+1,dq.push(a);
}
fill_n(vis,N,0);
if (x>par[x]&&y<par[y]) swap(x,y);
if (x>par[x]&&y>par[y]) cout<<"1\n";
else if (x<par[x]&&y<par[y]) cout<<"0\n";
else cout<<"\n";
int p=y;
while (2*dst[p]-1>dst[y]) p=par[p];
dq.push(p);
while (dq.size()){
int v=dq.front();
dq.pop();
vis[v]=1;
for (auto a:adj[v]) if (!vis[a]) par[a]=v,dq.push(a);
}
fill_n(vis,N,0);
diam[p]=1;
int q=x;
while (q!=p) diam[q]=1,q=par[q];
q=y;
while (q!=p) diam[q]=1,q=par[q];
N--;
out(x),out(y);
x=par[x],y=par[y];
for (auto a:adj[x]) if (!diam[a]) out(a);
for (auto a:adj[y]) if (!diam[a]) out(a);
int cur=x,oth=y;
bool side=0;
while (N){
out(cur);
cur=par[cur];
for (auto a:adj[cur]) if (!diam[a]) out(a);
for (int i=0;i<N;i++){
if (diam[par[i]]) continue;
bool f=1;
for (auto a:adj[i]) if (a!=par[i]&&!vis[a]) f=0;
if (f&&((side==0&&i<par[i])||(side==1&&i>par[i]))) out(i);
}
swap(cur,oth);
side=!side;
}
}
};
namespace part2{
void out(int x){
cout<<x<<'\n',N--;
}
void solve(){
cin.ignore(100, '\n');
string str;
getline(cin,str);
N--;
int l,r;
{
int a,b;cin>>a>>b;
if (str==""||str=="0") out(min(a,b)),l=max(a,b);
else out(max(a,b)),l=min(a,b);
}
{
int a,b;cin>>a>>b;
if (str=="0") out(min(a,b)),r=max(a,b);
else out(max(a,b)),r=min(a,b);
}
int a,b;
cin>>a>>b;
while (N){
if (a!=l&&b!=l) break;
out(a==l?b:a);
if (N) cin>>a>>b;
else break;
}
while (N){
if (a!=r&&b!=r) break;
out(a==r?b:a);
if (N) cin>>a>>b;
else break;
}
int cur=r,oth=l;
bool side=0;
while (N){
if (cur==oth){
out(a==cur?b:a);
if (N) cin>>a>>b;
else break;
continue;
}
if (a==oth||b==oth){
side=!side;
swap(cur,oth);
out(cur);
cur=a==cur?b:a;
if (N) cin>>a>>b;
else break;
continue;
}
if (a==cur||b==cur) out(a==cur?b:a);
else{
if (side==0) out(min(a,b));
else out(max(a,b));
}
if (N) cin>>a>>b;
else break;
}
}
};
int main() {
cin>>P>>N;
if (P==1) part1::solve();
else part2::solve();
}
