#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=130050,inf=1e9;
vector<pair<pair<int,int>,int>>edges;
int Idx(int u,int v){
if(u>v)swap(u,v);
pair<pair<int,int>,int>nesto={{u,v},0};
int lb=lower_bound(edges.begin(),edges.end(),nesto)-edges.begin();
return edges[lb].se;
}
vector<int>E[N];
vector<int>temp;
int n,m;ll D,A,B;
vector<int>E1[N],E2[N];
vector<int>grane1,grane2;
int depth1[N],depth2[N];
int strana[N];
void DFS1(int u,int parent=-1){
for(auto i:E1[u]){
if(i==parent||strana[i]==2) continue;
grane1.pb(Idx(u,i));
DFS1(i,u);
}
}
void DFS2(int u,int parent=-1){
for(auto i:E2[u]){
if(i==parent||strana[i]==1) continue;
grane2.pb(Idx(u,i));
DFS2(i,u);
}
}
void find_pair(int n1, std::vector<int> U, std::vector<int> V, int A1, int B1){
n=n1,m=U.size(),A=A1,B=B1;
for(int i=0;i<m;i++){int u=U[i],v=V[i];if(u>v) swap(u,v);edges.pb({{u,v},i});E[u].pb(v),E[v].pb(u);}
sort(edges.begin(),edges.end());
temp.resize(m);for(int i=0;i<m;i++) temp[i]=0;
D=ask(temp)/A;
int l=0,r=m-1;
int u,v,Ind;
while(l<=r){
int mid=l+r>>1;
for(int i=0;i<m;i++) temp[i]=0;
for(int i=0;i<=mid;i++) temp[i]=1;
ll x=ask(temp);
if(x>D*A){u=U[mid],v=V[mid],Ind=mid;r=mid-1;}
else l=mid+1;
}
queue<int>kju;
kju.push(u);
for(int i=0;i<n;i++) depth1[i]=inf;depth1[u]=0;
while(!kju.empty()){
int c=kju.front();kju.pop();
for(auto i:E[c]){
if(depth1[i]<=depth1[c]+1) continue;
depth1[i]=depth1[c]+1;
E1[c].pb(i);
kju.push(i);
}
}
kju.push(v);
for(int i=0;i<n;i++) depth2[i]=inf;depth2[v]=0;
while(!kju.empty()){
int c=kju.front();kju.pop();
for(auto i:E[c]){
if(depth2[i]<=depth2[c]+1) continue;
depth2[i]=depth2[c]+1;
E2[c].pb(i);
kju.push(i);
}
}
for(int i=0;i<n;i++) strana[i]=depth1[i]<depth2[i]?1:2;
DFS1(u);
DFS2(v);
l=0,r=grane1.size();
int S=u,T=v;
while(l<=r){
int mid=l+r>>1;
for(int i=0;i<m;i++) temp[i]=1;
for(auto i:grane2) temp[i]=0;
temp[Ind]=0;
for(int i=0;i<grane1.size();i++) temp[grane1[i]]=(i+1<=mid)?0:1;
ll x=ask(temp);
if(x>A*D) l=mid+1;
else{
r=mid-1;
if(mid==0){S=u;continue;}
S=grane1[mid-1];
if(depth1[U[S]]>depth1[V[S]]) S=U[S];
else S=V[S];
}
}
l=0,r=grane2.size();
while(l<=r){
int mid=l+r>>1;
for(int i=0;i<m;i++) temp[i]=1;
for(auto i:grane1) temp[i]=0;
temp[Ind]=0;
for(int i=0;i<grane2.size();i++) temp[grane2[i]]=(i+1<=mid)?0:1;
ll x=ask(temp);
if(x>A*D) l=mid+1;
else{
r=mid-1;
if(mid==0){T=v;continue;}
T=grane2[mid-1];
if(depth2[U[T]]>depth2[V[T]]) T=U[T];
else T=V[T];
}
}
answer(S,T);
}
