#include "highway.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int n,m,niv[100005],roots[5];
ll dist,AA,BB,d[3][100005];
int where[100005];
vector<pii> muchii[100005];
vector<pii> g;
vector<int> w;
ll memo[100005],calls;
bool inarb[300005],inx[300005];
int IND;
void bfs(int ind)
{
for(int i=0;i<n;i++)
d[ind][i]=1e9;
d[ind][roots[ind]]=0;
queue<int> coada;
coada.push(roots[ind]);
while(!coada.empty())
{
int nod=coada.front();
coada.pop();
for(auto i:muchii[nod])
if(d[ind][i.first]>d[ind][nod]+1)
{
d[ind][i.first]=d[ind][nod]+1;
coada.push(i.first);
}
}
}
ll buildniv(ll nivmax,ll ind)
{
for(int i=0;i<m;i++)
{
if(inarb[i]==0)
{
w[i]=1;
continue;
}
int a=g[i].first,b=g[i].second;
if(max(d[ind][a],d[ind][b])<=nivmax)
w[i]=0;
else
w[i]=1;
}
return ask(w);
}
ll buildx(int ind)
{
for(int i=0;i<m;i++)
{
if(inarb[i]==0)
{
w[i]=1;
continue;
}
int a=g[i].first,b=g[i].second;
if(d[ind][a]<d[ind][b])
swap(a,b);
if(inx[a])
w[i]=0;
else
w[i]=1;
}
return ask(w);
}
bool byniv(int i,int j)
{
int a=max(d[IND][g[i].first],d[IND][g[i].second]);
int b=max(d[IND][g[j].first],d[IND][g[j].second]);
return a<b;
}
int plsfind(int ind)
{
IND=ind;
for(int i=0;i<m;i++)
inarb[i]=0;
for(int i=0;i<n;i++)
d[ind][i]=1e9;
ll nivmax=0;
d[ind][roots[ind]]=0;
queue<int> coada;
coada.push(roots[ind]);
vector<int> edges;
while(!coada.empty())
{
int nod=coada.front();
nivmax=max(nivmax,d[ind][nod]);
coada.pop();
for(auto i:muchii[nod])
if(where[i.first]==ind&&d[ind][i.first]>d[ind][nod]+1)
{
d[ind][i.first]=d[ind][nod]+1;
inarb[i.second]=1;
edges.push_back(i.second);
coada.push(i.first);
}
}
//sort(edges.begin(),edges.end(),byniv);
for(int i=0;i<m;i++)
w[i]=1;
for(int j:edges)
w[j]=0;
/*ll val=ask(w);
if(val==dist*BB)
return roots[ind];*/
ll st=0;
ll dr=edges.size();
dr--;
ll ans=-1;
int poz=0;
while(st<=dr)
{
ll mij=(st+dr)/2;
for(int i=0;i<m;i++)
{
ll a=g[i].first,b=g[i].second;
if(a==roots[1]&&b==roots[2])
{
w[i]=0;
continue;
}
if(a==roots[2]&&b==roots[1])
{
w[i]=0;
continue;
}
if(where[a]!=where[b])
{
w[i]=1;
continue;
}
if(where[a]!=ind)
{
w[i]=0;
continue;
}
if(!inarb[i])
{
w[i]=0;
continue;
}
w[i]=1;
}
for(int j=0;j<=mij;j++)
w[edges[j]]=0;
ll x=ask(w);
int p=edges[mij];
int a=g[p].first;
int b=g[p].second;
if(x!=dist*AA)
st=mij+1;
else
{
poz=mij;
if(d[ind][a]<d[ind][b])
swap(a,b);
ans=a;
dr=mij-1;
}
}
if(ans==-1)
return roots[ind];
return ans;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
AA=A;
BB=B;
n=N;
m=U.size();
for(int i=0;i<m;i++)
{
int a=U[i],b=V[i];
g.push_back({a,b});
muchii[a].push_back({b,i});
muchii[b].push_back({a,i});
}
w.resize(m);
dist=ask(w)/A;
ll st=0;
ll dr=m-1;
while(st<=dr)
{
ll mij=(st+dr)/2;
for(int i=0;i<m;i++)
{
if(i<=mij)
w[i]=1;
else
w[i]=0;
}
ll val=ask(w);
if(val>dist*A)
{
roots[1]=g[mij].first;
roots[2]=g[mij].second;
dr=mij-1;
}
else
st=mij+1;
}
bfs(1);
bfs(2);
for(int i=0;i<n;i++)
{
if(d[1][i]<d[2][i])
where[i]=1;
if(d[2][i]<d[1][i])
where[i]=2;
}
int S=plsfind(1);
int T=plsfind(2);
answer(S,T);
}
