#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],pp[MAXN];
bool root[MAXN];
int find(int n,vector<int> U,vector<int> V,int pos,int nex,long long dist)
{
int m=U.size();
vector<int> vi(m);
for(auto& v:vi) v=1;
queue<int> Q;
for(int i=0;i<n;i++) dp[i]=INFi,root[i]=false,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);
if(dp[v.first]==1) root[v.first]=(v.first==nex);
else root[v.first]|=root[a];
}
else if(dp[v.first]==dp[a]+1) root[v.first]|=root[a];
for(auto v:ds[a]) if(dp[a]==dp[v.first]+1) vp[a].push_back(v.second),vi[v.second]=0;
}
int cc=0;
for(int i=0;i<n;i++) if(root[st[i]]) pp[cc++]=st[i];
int l=0,r=cc-1,p=0;
while(l<=r)
{
int mid=(l+r)/2;
vector<int> res=vi;
for(int j=0;j<=mid;j++) for(auto v:vp[pp[cc-j-1]]) res[v]=1;
if(ask(res)==dist) l=mid+1;
else r=mid-1,p=mid;
}
return pp[cc-p-1];
}
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);
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) pos+=(1<<i);
}
int x=find(n,U,V,V[pos],U[pos],dist),y=find(n,U,V,U[pos],V[pos],dist);
answer(x,y);
}
