#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
int n,m,q[150005],h,ta,t[150005],viz[150005],p[150005],v2[150005];
vector<int>g,v3[150005];
void find_pair(int n2,vector<int>u,vector<int>v,int a,int b){
int i;
n=n2;
m=u.size();
g.resize(m);
for(i=0;i<m;i++) {
g[i]=0;
v3[u[i]].push_back(v[i]);
v3[v[i]].push_back(u[i]);
}
long long l=ask(g);
int st=0,dr=n-2,mij,r=n-1;
while(st<=dr){
mij=(st+dr)/2;
if (dr-st>60000)
mij=60000;
for(i=0;i<m;i++){
if (u[i]>mij || v[i]>mij)
g[i]=1;
else
g[i]=0;
}
if (ask(g)==l)
r=mij,dr=mij-1;
else
st=mij+1;
}
int root=r;
q[++ta]=root;
viz[root]=1;
t[root]=-1;
while(h<ta){
int x=q[++h];
for(auto it:v3[x]){
if (!viz[it]){
viz[it]=1;
q[++ta]=it;
t[it]=x;
}
}
}
for(i=0;i<m;i++){
if (t[u[i]]==v[i])
p[u[i]]=i;
if (t[v[i]]==u[i])
p[v[i]]=i;
}
st=1;
dr=ta-1;
r=ta;
while(st<=dr){
mij=(st+dr)/2;
if (dr-st>60000)
mij=60000;
for(i=0;i<m;i++)
g[i]=1;
for(i=2;i<=mij;i++)
g[p[q[i]]]=0;
if (ask(g)==l)
r=mij,dr=mij-1;
else
st=mij+1;
}
int rb=q[r];
int tp=rb;
while(tp!=root){
v2[p[tp]]=1;
tp=t[tp];
}
st=1;
dr=r-1;
while(st<=dr){
mij=(st+dr)/2;
for(i=0;i<m;i++){
if (!v2[i])
g[i]=1;
else
g[i]=0;
}
for(i=2;i<=mij;i++)
g[p[q[i]]]=0;
if (ask(g)==l)
r=mij,dr=mij-1;
else
st=mij+1;
}
int ra=q[r];
answer(ra,rb);
}
