#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge {
ll u, v;
bool operator<(const Edge& other) const {
return make_pair(min(u, v), max(u, v)) < make_pair(min(other.u, other.v), max(other.u, other.v));
}
};
// --- ANN'S LOGIC (ENCODER) ---
void run_ann(ll n) {
vector<set<ll>> adj(n);
vector<ll> degree(n, 0);
for (int i = 0; i < n - 1; i++) {
ll u, v; cin >> u >> v;
adj[u].insert(v);
adj[v].insert(u);
degree[u]++; degree[v]++;
}
// Identify initial leaves and their edges
vector<Edge> typeA, typeB;
vector<vector<ll>> initial_leaf_list(n);
for (int i = 0; i < n; i++) {
if (degree[i] == 1) {
ll neighbor = *adj[i].begin();
initial_leaf_list[neighbor].push_back(i);
}
}
// Group leaves to decide the 1-bit message (the "flag")
for (int i = 0; i < n; i++) {
if (!initial_leaf_list[i].empty()) {
ll leaf = initial_leaf_list[i][0];
if (i < leaf) typeA.push_back({i, leaf});
else typeB.push_back({leaf, i});
}
}
sort(typeA.begin(), typeA.end());
sort(typeB.begin(), typeB.end());
// Determine the flag: Helps Kathrin handle the very first move
bool flag = (typeB.empty() || (!typeA.empty() && typeA.back() < typeB[0]));
cout << (flag ? 1 : 0) << endl;
auto remove_leaf = [&](ll leaf, ll neighbor, auto& self_q) {
cout << leaf << endl;
adj[neighbor].erase(leaf);
degree[neighbor]--;
if (degree[neighbor] == 1) {
// If neighbor becomes a new leaf, it's added to a queue for later
return true;
}
return false;
};
// Removal process following the sorted order
auto process_neighbor = [&](ll neighbor, queue<ll>& q) {
for (ll leaf : initial_leaf_list[neighbor]) {
if (remove_leaf(leaf, neighbor, q)) q.push(neighbor);
}
initial_leaf_list[neighbor].clear();
};
queue<ll> pending_leaves;
if (flag) for (auto& e : typeA) process_neighbor(e.u, pending_leaves);
for (auto& e : typeB) process_neighbor(e.v, pending_leaves);
if (!flag) for (auto& e : typeA) process_neighbor(e.u, pending_leaves);
while (!pending_leaves.empty()) {
ll u = pending_leaves.front(); pending_leaves.pop();
if (degree[u] == 1) {
ll neighbor = *adj[u].begin();
process_neighbor(neighbor, pending_leaves);
}
}
}
// --- KATHRIN'S LOGIC (DECODER) ---
void run_kathrin(ll n) {
string bit_msg; cin >> bit_msg;
bool flag = (bit_msg[0] == '1');
vector<ll> last_seen_time(n, 0);
pair<ll, ll> first_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_time[a] == 0 && last_seen_time[b] == 0) {
// Case: Brand new edge, use the flag
pair<ll, ll> current = {min(a, b), max(a, b)};
if (first_edge.first != -1 && current < first_edge) flag = !flag;
first_edge = current;
pick_b = flag;
} else {
// Case: We've seen one of these before.
// The one seen most recently is likely the neighbor, not the leaf.
pick_b = (last_seen_time[a] > last_seen_time[b]);
}
cout << (pick_b ? b : a) << endl;
last_seen_time[a] = last_seen_time[b] = ++timer;
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int phase; ll n;
if (!(cin >> phase >> n)) return 0;
if (phase == 1) run_ann(n);
else run_kathrin(n);
return 0;
}
