#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Using XOR sum is actually necessary for the memory/speed constraints
// and to mirror the original logic exactly, but I'll name it clearly.
struct Node {
ll neighbor_xor_sum = 0;
ll degree = 0;
};
void run_ann(ll n) {
vector<Node> tree(n);
for (int i = 0; i < n - 1; i++) {
ll u, v; cin >> u >> v;
tree[u].degree++; tree[v].degree++;
tree[u].neighbor_xor_sum ^= v;
tree[v].neighbor_xor_sum ^= u;
}
// leaf_pool[u] stores all leaves currently attached to node u
vector<vector<ll>> leaf_pool(n);
for (int i = 0; i < n; i++) {
if (tree[i].degree == 1) {
leaf_pool[tree[i].neighbor_xor_sum].push_back(i);
}
}
// A and B help decide the 1-bit message by looking at the FIRST leaf of each neighbor
vector<pair<ll, ll>> typeA, typeB;
for (int i = 0; i < n; i++) {
if (!leaf_pool[i].empty()) {
if (i < leaf_pool[i][0]) typeA.push_back({i, leaf_pool[i][0]});
else typeB.push_back({leaf_pool[i][0], i});
}
}
sort(typeA.begin(), typeA.end());
sort(typeB.begin(), typeB.end());
// This specific flag logic ensures Kathrin knows how to handle the start
bool flag = (typeB.empty() || (!typeA.empty() && typeA.back() > typeB[0]));
cout << (flag ? 1 : 0) << endl;
queue<ll> newly_formed_leaves;
auto process_leaf_removal = [&](ll leaf, ll neighbor) {
cout << leaf << endl;
tree[leaf].degree--;
tree[neighbor].degree--;
tree[neighbor].neighbor_xor_sum ^= leaf;
// If the neighbor becomes a leaf, it's ready to be processed later
if (tree[neighbor].degree == 1) {
newly_formed_leaves.push(neighbor);
leaf_pool[tree[neighbor].neighbor_xor_sum].push_back(neighbor);
}
};
auto clear_neighbor_leaves = [&](ll neighbor) {
for (ll leaf : leaf_pool[neighbor]) {
process_leaf_removal(leaf, neighbor);
}
leaf_pool[neighbor].clear();
};
// The order of execution here is CRITICAL for the 1-bit communication
if (flag) for (auto& p : typeA) clear_neighbor_leaves(p.first);
for (auto& p : typeB) clear_neighbor_leaves(p.second);
if (!flag) for (auto& p : typeA) clear_neighbor_leaves(p.first);
while (!newly_formed_leaves.empty()) {
ll leaf = newly_formed_leaves.front();
newly_formed_leaves.pop();
if (tree[leaf].degree != 0) {
clear_neighbor_leaves(tree[leaf].neighbor_xor_sum);
}
}
}
void run_kathrin(ll n) {
string bit_msg; cin >> bit_msg;
bool flag = (bit_msg[0] == '1');
vector<ll> last_seen_at(n, 0);
pair<ll, ll> reference_edge = {-1, -1};
ll timer = 1;
for (int i = 0; i < n - 1; i++) {
ll a, b; cin >> a >> b;
bool pick_b;
if (last_seen_at[a] == 0 && last_seen_at[b] == 0) {
// The logic for the "First Contact"
pair<ll, ll> current = {min(a, b), max(a, b)};
if (reference_edge.first != -1 && current < reference_edge) {
flag = !flag; // Toggle flag if the order of edges is inverted
}
reference_edge = current;
pick_b = flag;
} else {
// The "Recency" rule: pick the node we haven't just seen
// If last_seen_at[a] == timer, a was the neighbor in the previous step
pick_b = (last_seen_at[a] == timer || (last_seen_at[a] < last_seen_at[b] && last_seen_at[b] < timer));
}
cout << (pick_b ? b : a) << endl;
last_seen_at[a] = last_seen_at[b] = ++timer;
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int p; ll n; cin >> p >> n;
if (p == 1) run_ann(n);
else run_kathrin(n);
return 0;
}
