#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <utility>
#include "highway.h"
using namespace std;
vector < int > how;
vector < pair < int , int > > a,b;
vector < pair < int , int > > road[90005];
int n,m,x=-1,y=-1;
long long t;
bool have_V[90005]={0};
bool have_E[130005]={0};
int father[90005];
int Find(int here)
{
if(father[here]==here) return here;
father[here]=Find(father[here]);
return father[here];
}
int F(int l,int r)
{
//printf("%d %d\n",l,r);
//printf("%d %d\n",l,r);
int i;
for(i=l;i<=(l+r)/2;i++) how[i]=1;
if(ask(how)>t)
{
for(i=0;i<=(l+r)/2;i++) how[i]=0;
if(l==r) return l;
else return F(l,(l+r)/2);
}
else
{
for(i=l;i<=(l+r)/2;i++) how[i]=0;
if(l==r) return -1;
else return F((l+r)/2+1,r);
}
}
void Find1(int here)
{
//printf("a:%d\n",here);
for(auto i:road[here])
{
if(!have_V[i.first]&&have_E[i.second])
{
a.push_back(make_pair(i.second,i.first));
have_V[i.first]=1;
Find1(i.first);
}
}
}
void Find2(int here)
{
//printf("b:%d\n",here);
for(auto i:road[here])
{
if(!have_V[i.first]&&have_E[i.second])
{
b.push_back(make_pair(i.second,i.first));
have_V[i.first]=1;
Find2(i.first);
}
}
}
int Ans1(int l,int r)
{
//printf("a:%d %d\n",l,r);
int i;
if(l==r) return a[l].second;
for(i=(l+r)/2+1;i<=r;i++) how[a[i].first]=1;
if(ask(how)==t)
{
for(i=(l+r)/2+1;i<=r;i++) how[a[i].first]=0;
return Ans1(l,(l+r)/2);
}
else
{
for(i=(l+r)/2+1;i<=r;i++) how[a[i].first]=0;
return Ans1((l+r)/2+1,r);
}
}
int Ans2(int l,int r)
{
int i;
if(l==r) return b[l].second;
for(i=(l+r)/2+1;i<=r;i++) how[b[i].first]=1;
if(ask(how)==t)
{
for(i=(l+r)/2+1;i<=r;i++) how[b[i].first]=0;
return Ans2(l,(l+r)/2);
}
else
{
for(i=(l+r)/2+1;i<=r;i++) how[b[i].first]=0;
return Ans2((l+r)/2+1,r);
}
}
void find_pair(int N,vector < int > U,vector < int > V,int A,int B)
{
int i,edge;
n=N;
m=U.size();
for(i=0;i<n;i++) father[i]=i;
for(i=0;i<m;i++) how.push_back(0);
for(i=0;i<m;i++)
{
road[U[i]].push_back(make_pair(V[i],i));
road[V[i]].push_back(make_pair(U[i],i));
}
t=ask(how);
edge=F(0,m-1);
have_V[U[edge]]=1;
have_V[V[edge]]=1;
have_E[edge]=1;
father[U[edge]]=V[edge];
for(i=0;i<m;i++)
{
if(Find(U[i])!=Find(V[i]))
{
have_E[i]=1;
father[Find(U[i])]=Find(V[i]);
}
}
a.push_back(make_pair(edge,U[edge]));
b.push_back(make_pair(edge,V[edge]));
//x=U[edge];
//y=v[edge];
Find1(U[edge]);
Find2(V[edge]);
/*printf("a");
for(auto i:a) printf("%d ",i.first);
printf("\n");*/
/*printf("b");
for(auto i:b) printf("%d ",i.first);
printf("\n");*/
x=Ans1(0,a.size()-1);
y=Ans2(0,b.size()-1);
answer(x,y);
//printf("%d %d %d\n",edge,U[edge],V[edge]);
}
