#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
#include "thief.h"
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
vector<vector<pair<int, int>>> g;
vector<int> is_off, sajz, par, ip, Zbior;
void sajz_dfs(int v, int p) {
sajz[v] = 1;
for(auto[u,k] : g[v]) {
if(is_off[u] || u==p) continue;
par[u] = v;
ip[u] = k;
sajz_dfs(u,v);
sajz[v] += sajz[u];
}
}
ll find_centroid(ll v, ll ts) {
for(auto[u,k] : g[v]) {
if(is_off[u]) continue;
if(u==par[v]) {
if(ts-sajz[v] > ts/2) return find_centroid(u,ts);
} else {
if(sajz[u] > ts/2) return find_centroid(u,ts);
}
}
return v;
}
void V_dfs(int v, int p) {
Zbior.push_back(v);
for(auto[u,k] : g[v]) {
if(is_off[u] || u==p) continue;
V_dfs(u,v);
}
}
vector<int> post,vis,res;
void post_dfs(int v) {
if(vis[v]) return;
vis[v] = 1;
for(auto[u,k] : g[v]) if(k%2 == res[k/2]) post_dfs(u);
post.push_back(v);
}
void solve(int N, int M, std::vector<int> U, std::vector<int> V) {
int n = N; int m = M;
is_off.assign(n,0);
sajz.assign(n,0);
g.assign(n, {});
par.assign(n, 0);
ip.assign(n, 0);
for(int i=0; i<n-1; ++i) {
int a = U[i];
int b = V[i];
g[a].push_back({b, 2*i});
g[b].push_back({a, 2*i+1});
}
vector<int> curr;
curr.push_back(0);
while(1) {
vector<int> nxt;
vector<vector<int>> change(3);
for(auto VV : curr) {
int v = VV;
sajz_dfs(v,v);
v = find_centroid(v,sajz[v]);
sajz_dfs(v,v);
vector<pair<int, int>> nei;
for(auto[u,k] : g[v]) {
if(is_off[u]) continue;
nei.push_back({sajz[u], u});
}
vector<vector<int>> part(3);
int idx = 0, sum = 0;
int S = sajz[v];
for(int i=0; i<(int)nei.size(); ++i) {
if(nei[i].first + sum > sajz[v]/2) {
idx++;
sum = 0;
}
part[idx].push_back(nei[i].second);
sum += nei[i].first;
}
vector<vector<int>> whole(3);
for(int k=0; k<3; ++k) {
while(Zbior.size()) Zbior.pop_back();
for(auto u : part[k]) {
V_dfs(u, v);
}
whole[k] = Zbior;
}
/*for(int i=0; i<3; ++i) {
for(auto x : whole[i]) cerr << x << " ";
cerr << "\n";
}*/
for(int k=0; k<3; ++k) {
for(int l=0; l<3; ++l) {
for(auto x : whole[l]) {
change[k].push_back((ip[x]^(l==k)));
}
}
}
for(auto[u,k] : g[v]) {
if(is_off[u]) continue;
nxt.push_back(u);
}
is_off[v] = 1;
}
for(auto vec : change) {
vector<int> Q(m,0);
for(auto x : vec) Q[x/2] = x%2;
if(query(Q)) {
res = Q;
while(nxt.size()) nxt.pop_back();
// cerr << "hurra\n";
break;
}
}
break; // waznaer sfdgg asfg asdfg adrf
if(nxt.empty()) break;
swap(curr, nxt);
}
// for(int i=0; i<n-1; ++i) cerr << res[i] << " "; cerr << "\n";
while(post.size()) post.pop_back();
vis.assign(n, 0);
for(int i=0; i<n; ++i) post_dfs(i);
reverse(post.begin(), post.end());
vector<int> topo;
for(auto v : post) {
for(auto[u,k] : g[v]) {
if(res[k/2] == k%2) topo.push_back(k/2);
}
}
// for(auto x : topo) cerr << x << " "; cerr << "\n";
int lo = 0;
int hi = n-1;
while(lo < hi) {
vector<int> Q = res;
int mid = (lo+hi)/2;
for(int i=0; i<=mid; ++i) Q[topo[i]] ^= 1;
if(query(Q)) lo = mid+1;
else hi = mid;
}
lo = topo[lo];
int A = (res[lo] ? V[lo] : U[lo]);
reverse(topo.begin(), topo.end());
lo = 0;
hi = n-1;
while(lo < hi) {
vector<int> Q = res;
int mid = (lo+hi)/2;
for(int i=0; i<=mid; ++i) Q[topo[i]] ^= 1;
if(query(Q)) lo = mid+1;
else hi = mid;
}
lo = topo[lo];
int B = (res[lo] ? U[lo] : V[lo]);
// cerr << A << " " << B << "\n";
answer(A,B);
}
