#include<bits/stdc++.h>
using namespace std ;
const int N = 1005 ;
int p , n , deg[N] , par[N] , vis[N] ;
string s ;
vector<int> nei[N] , path ;
void dfs(int node){
vis[node] = 1 ;
for(int i:nei[node]){
if(!vis[i]) deg[node]++ , par[i]=node , dfs(i) ;
}
}
void A(){
for(int i=1 ; i<n ; i++){
int a , b ; cin >> a >> b ;
nei[a].push_back(b) ; nei[b].push_back(a) ;
}
memset(par,-1,sizeof(par)) ;
dfs(0) ;
memset(vis,0,sizeof(vis)) ;
queue<int> q ;
for(int i=0 ; i<n ; i++){
if(!deg[i]) continue ;
for(int j:nei[i]){
if(deg[j]) continue ;
q.push(j) ; // vis[j] = 1 ;
// if(j<par[j]) s+='0' ;
// else s+='1' ;
}
}
// sort?
while(!q.empty()){
int k = q.front() ; q.pop() ;
path.push_back(k) ;
for(int i:nei[k]){
if(vis[i]) continue ;
deg[i]-- ;
if(!deg[i]) q.push(i) , vis[i] = 1 ;
}
}
path.pop_back() ;
for(int i=1 ; i<n ; i++) s+='0' ;
for(int i=0 ; i<path.size() ; i++){
if(path[i]>par[path[i]]) s[i]='1' ;
}
cout << s << endl ;
for(int i:path) cout << i << ' ' ;
cout << endl ;
}
void B(){
cin >> s ;
int pos = 0 , lastx = -1 , lasty = -1 , x , y ;
for(int i=1 ; i<n ; i++){
cin >> x >> y ;
if(s[i-1]=='0') cout << x << endl ;
else cout << y << endl ;
continue ; //
if(lastx==x || lasty==x || vis[y]) cout << y << endl ;
else if(lastx==y || lasty==y || vis[x]) cout << x << endl ;
else if(s[pos++]=='0') cout << x << endl ;
else cout << y << endl ;
vis[x] = vis[y] = 1 ;
lastx = x , lasty = y ;
}
}
int main(){
cin >> p >> n ;
if(p==1) A() ;
else B() ;
return 0 ;
}
