#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fs first
#define sc second
using namespace std;
const int MAXN = 200005;
vector<pair<int,int>> adj[MAXN];
vector<int> ord, who, c, w;
int N, M, tmr;
ll W;
void build(int root, int par){
fill(ord.begin(), ord.end(), -1);
fill(who.begin(), who.end(), -1);
fill(c.begin(), c.end(), -1);
tmr = 0;
vector<int> stv, stp, it;
stv.pb(root);
stp.pb(par);
it.pb(0);
while(stv.size()){
int v = stv.back(), p = stp.back(), &idx = it.back();
if(idx == (int)adj[v].size()){
stv.pop_back();
stp.pop_back();
it.pop_back();
continue;
}
int eid = adj[v][idx].fs;
int to = adj[v][idx].sc;
idx++;
if(to == p) continue;
ord[eid] = tmr;
who[tmr] = eid;
c[tmr] = to;
tmr++;
stv.pb(to), stp.pb(v), it.pb(0);
}
}
int get1(){
int lb = 0, ub = M - 1;
while(lb < ub){
int mid = (lb + ub) / 2;
for(int i = 0; i < M; i++){
w[i] = (ord[i] != -1 && ord[i] <= mid);
}
if(ask(w) != W) ub = mid;
else lb = mid + 1;
}
return who[lb];
}
int get2(int root, int par){
build(root, par);
int lb = -1, ub = tmr - 1;
while(lb < ub){
int mid = (lb + ub + 1) / 2;
for(int i = 0; i < M; i++){
w[i] = (ord[i] >= mid);
}
if(ask(w) != W) lb = mid;
else ub = mid - 1;
}
return lb;
}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B){
N = n;
M = (int)U.size();
for(int i = 0; i < N; i++) adj[i].clear();
for(int i = 0; i < M; i++){
adj[U[i]].pb({i, V[i]});
adj[V[i]].pb({i, U[i]});
}
ord.assign(M, -1);
who.assign(M, -1);
c.assign(M, -1);
w.assign(M, 0);
W = ask(w);
build(0, -1);
int e = get1();
int x = U[e], y = V[e];
int lx = get2(x, y);
int s = (lx == -1 ? x : c[lx]);
int ly = get2(y, x);
int t = (ly == -1 ? y : c[ly]);
answer(s, t);
}
