#include "highway.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+1;
vec<pii> g[N];
int p[N];
void find_pair(int n,vec<int> _v,vec<int> _u,int a,int b){
int m=sz(_u);
int l=0,r=m;
vec<int>kek(m,1);
ll dst=ask(kek);
auto check=[&](vec<int> ids){
vec<int> w(m,1);
for(auto &z : ids) w[z]=0;
return ask(w);
};
while(l!=r){
int tm=(l+r)>>1;
vec<int>ids;
for(int j=0;j<=tm;j++)
ids.pb(j);
if(check(ids)<dst)
r=tm;
else
l=tm+1;
}
for(int i=0;i<m;i++){
g[_v[i]].pb({_u[i],i});
g[_u[i]].pb({_v[i],i});
}
int v=_v[l],u=_u[l];
queue<int>q;
vec<int>d1(n,2e9),d2(n,2e9);
vec<int>p1(n),p2(n);
p1[v]=l;d1[v]=0;
q.push(v);
while(!q.empty()){
int ct=q.front();q.pop();
for(auto &z : g[ct]){
if(d1[z.f]>d1[ct]+1){
d1[z.f]=d1[ct]+1;
p1[z.f]=z.s;
q.push(z.f);
}
}
}
p2[u]=l;d2[u]=0;
q.push(u);
while(!q.empty()){
int ct=q.front();q.pop();
for(auto &z : g[ct]){
if(d2[z.f]>d2[ct]+1){
d2[z.f]=d2[ct]+1;
p2[z.f]=z.s;
// cout<<"P@ "<<z.f<<' '<<z.s<<endl;
q.push(z.f);
}
}
}
///find s
vec<int>p;
vec<int> toadd;
for(int i=0;i<n;i++){
if(d1[i]<d2[i]) p.pb(i);
else if(d2[i]<d1[i]) toadd.pb(p2[i]);
}
sort(all(p),[&](int i,int j){return d1[i]<d1[j];});
l=0,r=sz(p)-1;
ll cnt=dst/b;
ll need=cnt*a;
while(l!=r){
int tm=(l+r)>>1;
vec<int>ids;
for(int j=0;j<=tm;j++) ids.pb(p1[p[j]]);
for(auto &j : toadd) ids.pb(j);
if(check(ids)!=need) l=tm+1;
else r=tm;
}
toadd.clear();
// --l;
int s=p[l];
p.clear();
for(int i=0;i<n;i++){
// cout<<d1[i]<<' '<<d2[i]<<endl;
if(d2[i]<d1[i]) p.pb(i);
else if(d1[i]<d2[i]) toadd.pb(p1[i]);
}
sort(all(p),[&](int i,int j){return d2[i]<d2[j];});
// for(auto &z : p)
// cout<<z<<' '<<d2[z]<<endl;
// cout<<"CHS "<<check(toadd)<<endl;
l=0,r=sz(p)-1;
while(l!=r){
int tm=(l+r)>>1;
vec<int>ids;
for(int j=0;j<=tm;j++) ids.pb(p2[p[j]]);
// cout<<"SZ "<<sz(toadd)<<endl;
for(auto &j : toadd) ids.pb(j);
// cout<<"AUE "<<check(ids)<<' '<<need<<' '<<tm<<endl;
if(check(ids)!=need) l=tm+1;
else r=tm;
}
int t=p[l];
// assert(check({p2[16565]}));
// cout<<"V "<<v<<' '<<u<<endl;
// cout<<"AS "<<s<<' '<<t<<' '<<d2[16565]<<' '<<d1[16565]<<endl;
answer(s,t);
}
/*
*/
