#include "highway.h"
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<random>
using namespace std;
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vp vector<pi>
#define vvp vector<vp>
vvp Adj;
vi CZ;
vi P;
vi w;
int root;
int s, t, m;
ll disa;
mt19937 mt(12309142);
void print(vi &L) {
cerr << "{";
for (auto i : L) cerr << i << ", ";
cerr << "}" << endl;
}
void print(vp &L) {
cerr << "{";
for (auto i : L) cerr << "{" << i.first << ", " << i.second << "}, ";
cerr << "}\n";
}
int dfs(int p, int dfp) {
P[p] = dfp;
int a = 1;
for (auto [i, _] : Adj[p]) {
if (i == dfp) continue;
a += dfs(i, p);
}
return CZ[p] = a;
}
int oink(int p, int l, int r, int sz) {
//cerr << "oink(" << p << ", " << l << ", " << r << ", " << sz << ")" << endl;
//cerr << "Adj[p] : ";
if (Adj[p][r-1].first == P[p]) r--;
if (Adj[p][l].first == P[p]) l++;
//print(Adj[p]);
if (l >= r) return p;
if (l+1 == r) {
int c = Adj[p][l].first;
w = vi(m, 0);
w[Adj[p][l].second] = 1;
ll res = ask(w);
//cerr << "res : " << res << endl;
if (res == disa) return p;
return oink(c, 0, Adj[c].size(), CZ[c]);
}
w = vi(m, 0);
int k = 0;
int i = l;
for (; i < r-1; i++) {
if (Adj[p][i].first == P[p]) continue;
if ((sz-1)/2 < k) break;
k += CZ[Adj[p][i].first];
w[Adj[p][i].second] = 1;
}
//cerr << "l : " << l << ", i : " << i << endl;
ll res = ask(w);
//cerr << "res : " << res << endl;
if (res == disa) return oink(p, i, r, sz-k);
return oink(p, l, i, k);
}
void find_pair(int n, vi U, vi V, int A, int B) {
m = U.size();
Adj = vvp(n);
CZ = vi(n);
P = vi(n);
//root = mt()%n;
root = 0;
for (int i = 0; i < m; i++) {
Adj[V[i]].push_back({U[i], i});
Adj[U[i]].push_back({V[i], i});
}
for (int i = 0; i < n; i++) {
shuffle(Adj[i].begin(), Adj[i].end(), mt);
}
dfs(root, -1);
s = 0; t = -1;
w = vi(m, 0);
disa = ask(w);
//cerr << "disa : " << disa << endl;
t = oink(root, 0, Adj[root].size(), CZ[root]);
//cerr << s << " " << t << endl;
answer(s, t);
}
