#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,A,B,x,bo[200009],lef,rig,mid,dis[200009],fx[200009],C,D;
deque <int> de;
vector <int> dep[200009];
long long K,X;
vector <pair <int, int> > v[200009];
vector <int> U,V,vv;
long long ask(const std::vector<int> &w);
void answer(int s, int t);
void fun(){
int h=0;
for(h=0; h<b; h++) vv[h]=0;
for(h=1; h<=a; h++){
if(bo[h]==0) continue;
for(vector <pair <int, int> >::iterator it=v[h].begin(); it!=v[h].end(); it++){
vv[(*it).second]=1;
}
}
}
void rec(int q, int w){
int h=0;
if(q==w){
x=q;
return;
}
int mid=(q+w)/2;
for(h=q; h<=mid; h++){
bo[h]=1;
}
fun();
X=ask(vv);
if(K==X){
rec(mid+1,w);
}else{
for(h=q; h<=mid; h++){
bo[h]=0;
}
rec(q,mid);
}
}
int povna(int q){
x=q;
de.push_back(x);
dis[x]=1;fx[x]=1;
while(de.size()){
c=de.front();
de.pop_front();
for(vector <pair <int, int> >::iterator it=v[c].begin(); it!=v[c].end(); it++){
if(fx[(*it).first]==1) continue;
dis[(*it).first]=dis[c]+1;
fx[(*it).first]=1;
de.push_back((*it).first);
}
}
for(i=1; i<=a; i++){
dep[dis[i]].push_back(i);
}
lef=1;rig=a+1;
while(1){
if(lef+1>=rig) break;
mid=(lef+rig)/2;
for(i=1; i<=a; i++) bo[i]=0;
zx=mid;
for(j=a; j>=1; j--){
for(jj=0; jj<dep[j].size(); jj++){
if(zx==0) break;
zx--;
bo[dep[j][jj]]=1;
}
if(zx==0) break;
}
fun();
X=ask(vv);
if(K==X){
rig=mid;
}else{
lef=mid;
}
}
mid=lef+1;
zx=mid;xc=0;
for(j=a; j>=1; j--){
for(jj=0; jj<dep[j].size(); jj++){
if(zx==0) break;
zx--;
xc=dep[j][jj];
}
if(zx==0) break;
}
return xc;
}
void find_pair(int N, vector<int> UU, vector<int> VV, int AA, int BB) {
a=N;b=UU.size();
vv.resize(b);
for(i=0; i<UU.size(); i++){
U.push_back(UU[i]);V.push_back(VV[i]);
U[i]++;V[i]++;
v[U[i]].push_back(make_pair(V[i],i));
v[V[i]].push_back(make_pair(U[i],i));
}
for(i=0; i<b; i++) vv[i]=0;
K=ask(vv);
rec(1,a);
C=povna(x);
D=povna(C);
answer(C-1,D-1);
}
