#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MX = 90005;
#define sz(x) (ll)(x.size())
#define fi first
#define se second
typedef pair<ll,ll> ii;
vector<ii> vec[MX];
bitset<MX> vis,dead;
vector<ll> order,h;
ll d[MX],W[MX],p[MX];
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
for (ll i = 0; i < N-1; ++i)
{
vec[U[i]].push_back({V[i],i});
vec[V[i]].push_back({U[i],i});
}
queue<ll> q;
q.push(0);
vis[0]=1;
while(!q.empty()){
ll f=q.front();
q.pop();
for(auto it:vec[f]){
if(!vis[it.fi]){
d[it.fi]=d[f]+1;
//cerr<<it.fi<<","<<d[it.fi]<<"\n";
vis[it.fi]=1,q.push(it.fi);
order.push_back(it.se);
}
}
}
//cerr<<"zero "<<d[0]<<"\n";
for (ll i = 0; i < N-1; ++i)
if(d[U[i]]>d[V[i]])swap(U[i],V[i]);
vector<int> query(N-1,0);
ll l=0,r=N-2,K=ask(query),ans=-1;
while(l<=r){
fill(query.begin(),query.end(),0);
ll med=(l+r)>>1;
for (ll i = 0; i < med; ++i)
query[order[i]]=1;
if(ask(query)==K)ans=med,l=med+1;
else r=med-1;
}
ll lca=U[order[ans]];
q.push(lca);
order.clear();
while(!q.empty()){
ll f=q.front();
q.pop();
for(auto it:vec[f]){
if(d[it.fi]<d[f])continue;
q.push(it.fi);
p[it.fi]=f;
W[it.fi]=it.se;
order.push_back(it.se);
}
}
/*cerr<<"LCA : "<<lca<<"\n";
for(auto it:order){
cerr<<U[it]<<"-"<<V[it]<<"\n";
}*/
l=0,r=sz(order)-1,ans=-1;
while(l<=r){
fill(query.begin(),query.end(),1);
ll med=(l+r)>>1;
for (ll i = 0; i <= med; ++i)
query[order[i]]=0;
if(ask(query)==K)ans=med,r=med-1;
else l=med+1;
}
ll T=V[order[ans]];
if(d[T]==(K/A)){answer(lca,T);return ;}
ll node=T;
while(node!=lca){
//cerr<<node<<"\n";
dead[node]=1;
h.push_back(W[node]);
node=p[node];
}
q.push(lca);
order.clear();
while(!q.empty()){
ll f=q.front();
q.pop();
for(auto it:vec[f]){
if(d[it.fi]<d[f] ||dead[it.fi])continue;
q.push(it.fi);
order.push_back(it.se);
}
}
l=0,r=sz(order)-1,ans=-1;
/*for(auto it:h){
cerr<<U[it]<<"->"<<V[it]<<"\n";
}*/
while(l<=r){
fill(query.begin(),query.end(),1);
for(auto it:h)
query[it]=0;
ll med=(l+r)>>1;
for (ll i = 0; i <= med; ++i)
query[order[i]]=0;
if(ask(query)==K)ans=med,r=med-1;
else l=med+1;
}
answer(T,V[order[ans]]);
}
