#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> tree;
vector<int> par;
void dfs1(int node, int p) {
par[node] = p;
for (auto next: tree[node]) {
if (next == p) continue;
par[next] = p;
dfs1(next, node);
}
}
void encrypt_star() {
int root = 0;
for (int i = 1; i < n; i++) {
if (tree[i].size() > tree[root].size()) root = i;
}
if (root < tree[root][0]) cout << "00" << endl;
else cout << "11" << endl;
for (auto nxt: tree[root]) cout << nxt << " ";
cout << endl;
}
void encrypt() {
tree.resize(n+1);
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
int root = 0;
for (int i = 1; i < n; i++) {
if (tree[i].size() > tree[root].size()) {
root = i;
}
}
par.assign(n, -1);
dfs1(root, -1);
vector<pair<int, int>> leaves;
int done = -1;
for (int i = 0; i < n; i++) {
if (tree[i].size() == 1 && par[i] != root) {
leaves.push_back({i, par[i]});
done = i;
break;
}
}
if (done == -1) {
encrypt_star();
return;
}
for (int i = 0; i < n; i++) {
if (done == i) continue;
if (tree[i].size() == 1) {
leaves.push_back({i, par[i]});
}
}
if (leaves[0].first < leaves[0].second) cout << 0 << endl;
else cout << 1 << endl;
cout << leaves[0].first << " ";
int trig = par[leaves[0].first];
for (int i = 1; i < (int)leaves.size(); i++) {
if (leaves[i].first < leaves[i].second) {
cout << leaves[i].first << " ";
}
}
while (trig != root) {
cout << trig << " ";
trig = par[trig];
}
for (int i = 1; i < (int)leaves.size(); i++) {
if (leaves[i].first > leaves[i].second) {
cout << leaves[i].first << " ";
}
}
for (int i = 1; i < (int)leaves.size(); i++) {
int curr = par[leaves[i].first];
while (curr != -1 && curr != root) {
cout << curr << " ";
curr = par[curr];
}
}
cout << endl;
}
void decrypt_star(string s) {
int root = -1;
for (int i = 0; i < n-1; i++) {
int a, b; cin >> a >> b;
if (root == -1) {
if (s == "00") root = a;
else root = b;
}
cout << (a ^ b ^ root) << endl;
}
}
void decrypt() {
string s; cin >> s;
if (s.size() == 2) {
decrypt_star(s);
return;
}
int a, b; cin >> a >> b;
int trig;
if (s == "0") {
cout << a << endl;
trig = b;
}
else if (s == "1") {
cout << b << endl;
trig = a;
}
vector<bool> pends(n, false);
int root = -1;
bool flip = false;
bool prev = false;
for (int i = 1; i < n-1; i++) {
cin >> a >> b;
int chose;
if (prev && (a == root || b == root) && !pends[(a ^ b ^ root)]) {
cout << root << endl;
root = (a ^ b ^ root);
continue;
}
prev = false;
if (a == root || b == root) {
chose = a ^ b ^ root;
}
else if (a == trig || b == trig) {
cout << trig << endl;
if (flip == false)
flip = true;
prev = true;
root = (trig ^ a ^ b);
trig = -1;
continue;
}
else if (pends[a] && pends[b]) {
assert(false);
}
else if (pends[a]) {
chose = a;
}
else if (pends[b]) {
chose = b;
}
else {
if (!flip) chose = a;
else chose = b;
}
cout << chose << endl;
pends[(a ^ b ^ chose)] = true;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int p; cin >> p >> n;
if (p == 1) encrypt();
else decrypt();
return 0;
}
