#include "highway.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define x first
#define y second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pii>g[90015];
vector<ll>all[90015];
vector<int>qry,R1,R2;
ll n,m,mn,a,b,d,fa[90015],dep[90015];
void bfs(int r1,int r2){
queue<pii>q;
q.push({r1,r1}); q.push({r2,r2});
dep[r1]=1; dep[r2]=1;
while (!q.empty()){
auto [p,root]=q.front(); q.pop();
(root==r1 ? R1 : R2).push_back(p);
for (auto [i,idx]:g[p]){
if (!dep[i]){
dep[i]=dep[p]+1; fa[i]=idx;
q.push({i,root});
}
}
}
}
void solve(int u,int v){
fill(qry.begin(),qry.end(),1);
bfs(u,v);
int l=0,r=R1.size()-1;
for (auto i:R2)
qry[fa[i]]=0;
while (l<r){
int mid=(l+r)>>1;
for (int i=1;i<=mid;i++)
qry[fa[R1[i]]]=0;
ll dis=ask(qry);
if (dis==mn) r=mid;
else l=mid+1;
for (int i=1;i<=mid;i++)
qry[fa[R1[i]]]=1;
}
int s=R1[l];
// cout<<"find "<<s<<'\n';
fill(qry.begin(),qry.end(),1);
for (auto i:R1)
qry[fa[i]]=0;
l=0; r=R2.size()-1;
while (l<r){
int mid=(l+r)>>1;
for (int i=1;i<=mid;i++)
qry[fa[R2[i]]]=0;
ll dis=ask(qry);
if (dis==mn) r=mid;
else l=mid+1;
for (int i=1;i<=mid;i++)
qry[fa[R2[i]]]=1;
}
int t=R2[l];
// cout<<"answer "<<s<<" "<<t<<'\n';
answer(s,t);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n=N; m=U.size(); a=A; b=B;
for (int i=0;i<m;i++){
g[U[i]].push_back({V[i],i});
g[V[i]].push_back({U[i],i});
}
qry.resize(m,0);
mn=ask(qry); d=mn/A;
int l=0,r=m-1,u,v;
while (l<r){
int mid=(l+r)>>1;
for (int i=0;i<=mid;i++)
qry[i]=1;
ll now=ask(qry);
for (int i=0;i<=mid;i++)
qry[i]=0;
if (now!=mn) r=mid;
else l=mid+1;
}
u=U[l]; v=V[l];
fa[u]=l; fa[v]=l;
// cout<<"solve "<<u<<" "<<v<<'\n';
solve(u,v);
}
/*
./rand
./highway
*/
