#include<bits/stdc++.h>
using namespace std ;
const int N = 1005 ;
int p , n , deg[N] , par[N] ;
string s ;
vector<int> nei[N] , path ;
void dfs(int node){
for(int i:nei[node]){
if(i!=par[node]) 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) ;
queue<int> q ;
for(int i=0 ; i<n ; i++){
for(int j:nei[i]){
if(deg[j]) continue ;
q.push(j) ;
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(!deg[i]) continue ;
deg[i]-- ;
if(!deg[i]) q.push(i) ;
}
}
path.pop_back() ;
cout << s << endl ;
for(int i:path) cout << i << ' ' ;
cout << endl ;
}
void B(){
cin >> s ;
int pos = 0 , lastx = -1 , lasty = -1 , x , y ;
set<int> st ;
for(int i=1 ; i<n ; i++){
cin >> x >> y ;
if(lastx==x || lasty==x || st.find(y)!=st.end()) cout << y << endl ;
else if(lastx==y || lasty==y || st.find(x)!=st.end()) cout << x << endl ;
else if(s[pos++]=='0') cout << x << endl ;
else cout << y << endl ;
st.insert(x) , st.insert(y) ;
lastx = x , lasty = y ;
}
}
int main(){
cin >> p >> n ;
if(p==1) A() ;
else B() ;
return 0 ;
}
