#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;std::vector<int>u,v;std::vector<std::pair<int,int>>g[90001];
int sub12(int src,int ban)
{
vector<int>d(n,1e9),e(n,-1);
queue<pair<int,int>>q; q.emplace(d[src]=0,src);
while(q.size()){auto[c,u]=q.front();q.pop();for(auto[v,i]:g[u])if(ban-i&&d[v]>c+1)q.emplace(d[v]=c+1,v),e[v]=i;}
long long need; {vector<int>qq(m);for(int i=0;i<n;++i)if(~e[i])qq[e[i]]=1;need=ask(qq);}
vector<int>c;
for(int i=0;i<n;++i)if(d[i]<1e9)c.push_back(i);
sort(c.begin(),c.end(),[&d](int i,int v){return d[i]<d[v];});
int z=0,l=0,r=c.size()-1;
while(l<=r){
int y=(l+r)/2;
vector<int>qq(m,0);
for(int i=1;i<=y;++i)if(~e[c[i]])qq[e[c[i]]]=1;
if (ask(qq)==need)z=c[y],r=y-1;
else l=y+1;
}
return z;
}
void sub1234(){
long long need; {vector<int>qq(m,1); need=ask(qq);}
auto dt = need / b;
long long light = dt * a;
int e1,l=0,r=m-1;
while(l<=r) {
int y=(l+r)/2;
vector<int>qq(m);
for(int i=0;i<=y;++i)qq[i]=1;
if(ask(qq)>light)r=y-1,e1=y;
else l=y+1;
}
int p=u[e1],q=v[e1];
int s=sub12(p,e1);
int t=sub12(q,e1);
answer(s,t);
}
void find_pair(int n_, std::vector<int> u_, std::vector<int> v_, int A_, int B_) {
n=n_,u=u_,v=v_,a=A_,b=B_;m=u.size();
for(int i=0;i<m;++i)g[u[i]].push_back({v[i],i}),g[v[i]].push_back({u[i],i});
sub1234();
}
