#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define sz(x) (int) x.size()
#define pb push_back
#define all(x) (int)x.size()
const int MAXN=9e4+10;
typedef pair<int,int> pii;
vector<pii> g[MAXN];
int dep[MAXN],pai[MAXN],n,id[MAXN];
void dfs(int x){
for(auto [u,j]:g[x]) if(u!=pai[x]){
id[u]=j;
pai[u]=x;
dep[u]=dep[x]+1;
dfs(u);
}
}
void dfs1(int x){
for(auto [u,j]:g[x]) if(u!=pai[x]){
id[u]=j;
pai[u]=x;
dep[u]=dep[x]+1;
dfs1(u);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n=N;
fall(i,0,sz(U)-1){
g[U[i]].pb({V[i],i});
g[V[i]].pb({U[i],i});
}
vector<int> w(sz(U));
ll dist=ask(w);
pai[0]=-1;
dfs(0);
int ini=1,fim=n-1,mx=0;
while(ini<=fim){
int mei=(ini+fim)>>1;
fall(i,0,sz(U)-1){
w[i]=0;
if(max(dep[U[i]],dep[V[i]])>=mei) w[i]=1;
}
ll d=ask(w);
if(d==dist) fim=mei-1;
else ini=mei+1,mx=mei;
}
vector<int> cand;
fall(i,0,n-1) if(dep[i]==mx) cand.pb(i);
while(sz(cand)>1){
vector<int> ca[2];
for(auto&x:w) x=0;
fall(i,0,sz(cand)-1) ca[i%2].pb(cand[i]);
for(auto x:ca[0]) w[id[x]]=1;
ll d=ask(w);
if(d!=dist) cand=ca[0];
else cand=ca[1];
}
int ans1=cand[0];
pai[ans1]=-1,id[ans1]=dep[ans1]=0;
dfs1(ans1);
ll real=dist/A;
cand.clear();
fall(i,0,n-1) if(dep[i]==real) cand.pb(i);
while(sz(cand)>1){
vector<int> ca[2];
for(auto&x:w) x=0;
fall(i,0,sz(cand)-1){
ca[i%2].pb(cand[i]);
}
for(auto x:ca[0]) w[id[x]]=1;
ll d=ask(w);
if(d!=dist) cand=ca[0];
else cand=ca[1];
}
answer(ans1,cand[0]);
}
