//EGOI 2025 Laser Strike
//https://qoj.ac/contest/2344/problem/13172
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll,ll>;
void encode(ll n){
vll g[n], deg(n,0), X(n,0); ll a, b;
for(int i=0; i<n-1; i++){
cin >> a >> b;
g[a].push_back(b); g[b].push_back(a);
deg[a]++; deg[b]++; X[a]^=b; X[b]^=a;
}
queue<ll> q; vll leaf[n]; vector<pll> A, B;
for(int i=0; i<n; i++) if(deg[i]==1) leaf[X[i]].push_back(i);
auto remove=[&](ll v,ll u){
cout << v << endl;
deg[v]--; deg[u]--; X[u]^=v;
if(deg[u]==1) q.push(u), leaf[X[u]].push_back(u);
};
auto update=[&](ll u){
for(auto v:leaf[u]) remove(v,u);
leaf[u].clear();
};
for(int i=0; i<n; i++) if((ll)leaf[i].size()!=0){
if(i<leaf[i][0]) A.push_back({i,leaf[i][0]});
else B.push_back({leaf[i][0],i});
}
sort(A.begin(),A.end()); sort(B.begin(),B.end()); bool flag=(B.empty() || (!A.empty() && A.back()>B[0]));
cout << (flag?1:0) << endl;
if(flag) for(auto [v,u]:A) update(v);
for(auto [v,u]:B) update(u);
if(!flag) for(auto [v,u]:A) update(v);
while(!q.empty()){
auto v=q.front(); q.pop();
if(deg[v]!=0) update(X[v]);
}
}
void decode(ll n){
cin.ignore(100,'\n'); ll a, b, time=1;
string s; cin >> s; bool flag=s[0]-'0';
vll lst(n,0); pll lstEdge={-1,-1};
for(int i=0; i<n-1; i++){
cin >> a >> b; bool ans=(lst[a]==time || (lst[a]<lst[b] && lst[b]<time));
if(lst[a]==0 && lst[b]==0){
if(pll{a,b}<lstEdge) flag^=1;
lstEdge=pll{a,b}; ans=flag;
}
lst[a]=lst[b]=++time;
cout << (ans?b:a) << endl;
}
}
int main(){
ll p, n;
cin >> p >> n;
if(p==1) encode(n);
else decode(n);
return 0;
}
