#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 << " ";
for (int i = 1; i < (int)leaves.size(); i++) {
if (leaves[i].first < leaves[i].second) {
cout << leaves[i].first << " ";
}
}
cout << leaves[0].second << " ";
for (int i = 1; i < (int)leaves.size(); i++) {
if (leaves[i].first > leaves[i].second) {
cout << leaves[i].first << " ";
}
}
int curr = par[leaves[0].second];
while (curr != -1 && curr != root) {
cout << curr << " ";
curr = par[curr];
}
for (int i = 1; i < (int)leaves.size(); i++) {
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<int> pends(n, 0);
pends[(a ^ b ^ trig)] = 1;
bool flip = false;
for (int i = 1; i < n-1; i++) {
cin >> a >> b;
if (a == trig || b == trig) {
cout << trig << endl;
pends[(a ^ b ^ trig)] = i+1;
flip = true;
continue;
}
int chose;
if (pends[a] && pends[b]) {
if (pends[a] < pends[b]) {
chose = a;
}
else {
chose = b;
}
}
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)] = i+1;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int p; cin >> p >> n;
if (p == 1) encrypt();
else decrypt();
return 0;
}
