#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using ii = pair<int, int>;
using iii = pair<int, ii>;
using pvii = pair<vector<int>, ii>;
constexpr int MAXN = 20000 + 5;
constexpr int INF = 1e18 + 5;
constexpr int LOG = 20;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int P, N; cin >> P >> N;
if (P == 1) {
vector<vector<int>> adjlist(N);
for (int i = 0; i < N-1; ++i) {
int u, v; cin >> u >> v;
adjlist[u].emplace_back(v);
adjlist[v].emplace_back(u);
}
vector<int> leaves;
for (int i = 0; i < N; ++i) if (adjlist[i].size() == 1) leaves.emplace_back(i);
// line graph
if (leaves.size() == 2) {
int leaf = leaves[0];
int pa1 = adjlist[leaf][0];
if (!leaf || !pa1) {
leaf = leaves[1];
pa1 = adjlist[leaf][0];
}
cout << to_string(adjlist[leaf][0] > leaf) << endl;
vector<bool> seen(N);
for (int i = 0; i < N-1; ++i) {
cout << leaf << endl;
seen[leaf] = true;
for (int ch : adjlist[leaf]) {
if (!seen[ch]) {
leaf = ch;
break;
}
}
}
}
// star graph
else {
int root = 0;
sort(leaves.begin(), leaves.end());
for (int i : leaves) {
if (root == i) ++root;
}
cout << to_string(root == 0) << endl;
for (int i : leaves) cout << i << endl;
}
}
else {
cin.ignore(100, '\n');
string message;
getline(cin, message);
bool mbool = message == "1";
int a, b; cin >> a >> b;
// line graph
if (a && b) {
int ans = mbool ? min(a, b) : max(a, b);
cout << ans << endl;
ans = a ^ b ^ ans;
for (int i = 1; i < N - 1; ++i) {
int u, v; cin >> u >> v;
cout << ans << endl;
ans = u ^ v ^ ans;
}
}
else {
int root = mbool ? 0 : a | b;
cout << (a ^ b ^ root) << endl;
for (int i = 1; i < N-1; ++i) {
int u, v; cin >> u >> v;
cout << (u ^ v ^ root) << endl;
}
}
}
}
