#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)});
}
vector<int> anss;
int root=0;
for(int x=0;x<2;x++)
{
queue<int> q; v.clear();
memset(vis,0,sizeof vis);
q.push(root); vis[root]=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;
}
}
reverse(v.begin(), v.end());
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;
}
int s=v[ans]>0?V[v[ans]-1]:U[-v[ans]-1];
root=s; anss.push_back(s);
}
//cout << anss[0] << " " << anss[1] << endl;
answer(anss[0],anss[1]);
}
