#include"highway.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const int INFi=1e9;
vector< pair<int,int> > ds[MAXN];
vector<int> vp[MAXN];
int dp[MAXN],st[MAXN];
int find(int n,vector<int> U,vector<int> V,int pos,long long dist,int B)
{
int m=U.size();
vector<int> vi(m);
queue<int> Q;
for(int i=0;i<n;i++) dp[i]=INFi,vp[i].clear();
Q.push(pos),dp[pos]=0;
int cnt=0;
while(!Q.empty())
{
int a=Q.front();
Q.pop(),st[cnt++]=a;
for(auto v:ds[a]) if(dp[v.first]==INFi) dp[v.first]=dp[a]+1,Q.push(v.first);
}
for(int i=0;i<n;i++) for(auto v:ds[i]) if(dp[i]==dp[v.first]+1) vp[i].push_back(v.second);
else if(dp[i]!=dp[v.first]-1) vi[v.second]=true;
int r=0;
for(int i=16;i+1;i--) if(r+(1<<i)<n)
{
vector<int> res=vi;
for(int j=0;j<r+(1<<i);j++) for(auto v:vp[st[j]]) res[v]=1;
if(ask(res)!=dist*B) r+=(1<<i);
}
return st[r];
}
void find_pair(int n,vector<int> U,vector<int> V,int A,int B)
{
int m=U.size();
for(int i=0;i<m;i++) ds[U[i]].push_back({V[i],i}),ds[V[i]].push_back({U[i],i});
vector<int> vi(m);
long long dist=ask(vi)/A;
int pos=0;
for(int i=16;i+1;i--) if(pos+(1<<i)<m)
{
vector<int> res(m);
for(int j=0;j<pos+(1<<i);j++) res[j]=1;
if(ask(res)==dist*A) pos+=(1<<i);
}
int x=find(n,U,V,U[pos],dist,B),y=find(n,U,V,x,dist,B);
answer(x,y);
}
