#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int> v;
int vis[N];
vector<pair<int,int> > adj[N];
int par[N];
long long query(int l,int r,int m)
{
vector<int> vv(m,1);
for(int i=l;i<=r;i++)
vv[abs(v[i])-1]=0;
return ask(vv);
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int a, int b)
{
int m=U.size();
for(int i=0;i<m;i++)
{
adj[U[i]].push_back({V[i],(i+1)});
adj[V[i]].push_back({U[i],-(i+1)});
}
queue<int> q;
q.push(0); vis[0]=1;
while(q.size())
{
int x=q.front();
q.pop();
for(auto i:adj[x])
{
if(vis[i.first]) continue;
v.push_back(i.second);
q.push(i.first);
par[i.first]=x;
vis[i.first]=1;
}
}
long long f=query(0,v.size()-1,m);
/*for(int i=0;i<v.size();i++)
cout << v[i] << " ";
cout << endl;*/
int st=0,en=v.size()-1,ans=0;
while(st<=en)
{
int mid=(st+en)/2;
if(query(mid,v.size()-1,m)==f)
{
ans=mid; st=mid+1;
}
else
en=mid-1;
}
st=ans+1; en=v.size()-1; int ans2=v.size()-1;
while(st<=en)
{
int mid=(st+en)/2;
if(query(ans,mid,m)==f)
{
en=mid-1; ans2=mid;
}
else
st=mid+1;
}
//cout << v[ans] << " " << v[ans2] << endl;
int s=(v[ans]>0?V[abs(v[ans])-1]:U[abs(v[ans])-1]),t=(v[ans2]>0?V[abs(v[ans2])-1]:U[abs(v[ans2])-1]);
//cout << s << " " << t << endl;
int tt=t;
while(par[tt])
{
if(par[tt]==s) {s=par[s]; break;}
tt=par[tt];
}
swap(s,t);
tt=t;
while(par[tt])
{
if(par[tt]==s) {s=par[s]; break;}
tt=par[tt];
}
answer(s,t);
}
