#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int person, n;
int last_seen[maxn];
set<int> adj[maxn];
set<int> taken;
queue<int> leaves;
void delete_leaves(int x) {
vector<int> to_erase;
for (auto u: adj[x]) {
if (adj[u].size() == 1) {
to_erase.emplace_back(u);
adj[u].erase(x);
}
}
for (auto u: to_erase) {
adj[x].erase(u);
cout << u << endl;
}
if (adj[x].size() == 1) leaves.emplace(x);
}
void delete_self(int x) {
if (adj[x].size() == 0) {
return; //already deleted
}
int par = *adj[x].begin();
adj[par].erase(x);
adj[x].erase(par);
cout << x << endl;
delete_leaves(par);
}
void ann() {
int a, b;
for (int i = 1; i <= n - 1; i++) {
cin >> a >> b;
adj[a].emplace(b);
adj[b].emplace(a);
}
vector<pair<int, int>> smaller, larger;
for (int i = 0; i < n; i++) {
a = i;
if (adj[a].size() == 1) { //we are trying to remove a
b = *adj[a].begin();
if (taken.find(b) == taken.end()) {
if (a > b) {
larger.emplace_back(b, a);
} else {
smaller.emplace_back(a, b);
}
taken.emplace(b);
}
}
}
cerr << 1 << endl;
sort(smaller.begin(), smaller.end());
sort(larger.begin(), larger.end());
int larger_hash = -1, smaller_hash = -1;
if (larger.size()) {
larger_hash = larger.front().first * n + larger.front().second;
}
if (smaller.size()) {
smaller_hash = smaller.back().first * n + smaller.back().second;
}
if (smaller_hash > larger_hash) {
cout << 0 << endl;
for (auto [u, v]: smaller) {
leaves.emplace(u);
cerr << u << ' ' << v << ' ' << 0 << endl;
}
for (auto [u, v]: larger) {
leaves.emplace(v);
cerr << u << ' ' << v << ' ' << 1 << endl;
}
} else {
cout << 1 << endl;
for (auto [u, v]: larger) {
leaves.emplace(v);
cerr << u << ' ' << v << ' ' << 1 << endl;
}
for (auto [u, v]: smaller) {
leaves.emplace(u);
cerr << u << ' ' << v << ' ' << 0 << endl;
}
}
while (leaves.size() > 1) {
int a = leaves.front();
leaves.pop();
delete_self(a);
}
}
void kathrin() {
bool bit;
cin >> bit;
pair<int, int> prev_edge = {-1, -1};
int a, b;
memset(last_seen, 0, sizeof(last_seen));
int prev_hash = -1, hash = 0;
for (int i = 1; i <= n - 1; i++) {
cin >> a >> b;
if (last_seen[a] | last_seen[b]) {
if (prev_edge.first == a || prev_edge.second == a) {
cerr << "attached" << endl;
last_seen[a] = i;
cout << b; //delete all leaves attached to a
} else if (prev_edge.first == b || prev_edge.second == b) {
cerr << "attached" << endl;
last_seen[b] = i;
cout << a;
} else if (last_seen[a] > last_seen[b]){
cerr << "rule 3" << endl;
cout << a;
last_seen[b] = i;
} else {
cerr << "rule 3" << endl;
cout << b;
last_seen[a] = i;
}
}
else {
if (a > b) swap(a, b);
hash = a * n + b;
if (hash < prev_hash) bit = !bit;
if (bit) { //1 means higher, 0 means lower
cout << b;
last_seen[a] = i;
cerr << 11 << endl;
} else {
cout << a;
last_seen[b] = i;
cerr << 10 << endl;
}
prev_hash = hash;
}
cout << endl;
prev_edge = make_pair(a, b);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> person >> n;
if (person == 1) {
ann();
} else {
kathrin();
}
return 0;
}
