#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MAXN = 90010;
const int MAXM = 130010;
int n, m;
int A, B;
int color[MAXN];
int U[MAXM], V[MAXM];
vector< vector<int> > groups;
bool sameGroup()
{
vector<int> q( m , 0 );
for(int i = 0 ; i < m ; i++)
if( color[ U[i] ] == color[ V[i] ] ) q[i] = 1;
return ( ask(q)%2 == 0 );
}
void splitVector(vector<int>& v, vector<int>& L, vector<int>& R)
{
int m = (int)v.size()/2;
for(int i = 0 ; i < m ; i++)
L.push_back( v[i] );
for(int i = m ; i < (int)v.size() ; i++)
R.push_back( v[i] );
}
void splitGroups()
{
vector< vector<int> > aux( 2*groups.size() );
for(int i = 0 ; i < (int)groups.size() ; i++)
splitVector( groups[i] , aux[2*i] , aux[2*i + 1] );
groups = aux;
}
void paintGroup(vector<int>& nodes, int c)
{
for(int i = 0 ; i < (int)nodes.size() ; i++)
color[ nodes[i] ] = c;
}
void divideGroups()
{
while( true )
{
splitGroups();
for(int i = 0 ; i < (int)groups.size() ; i++)
paintGroup( groups[i] , i%2 );
if( !sameGroup() ) break;
}
}
bool testGroup(int k)
{
for(int i = 0 ; i < (int)groups.size() ; i++)
paintGroup( groups[i] , 0 );
for(int i = 0 ; i <= k ; i += 2)
paintGroup( groups[i] , 1 );
return !sameGroup();
}
int bsGroup()
{
int l = 0;
int r = ( (int)groups.size() - 1 )/2;
while( l < r )
{
int m = ( l + r )/2;
if( testGroup( 2*m ) ) r = m;
else l = m + 1;
}
return 2*r;
}
bool testNode(int g, int k)
{
for(int i = 0 ; i <= k ; i++)
color[ groups[g][i] ] = 1;
for(int i = k + 1 ; i < (int)groups[g].size() ; i++)
color[ groups[g][i] ] = 0;
return sameGroup();
}
int bsNode(int g)
{
int l = 0;
int r = (int)groups[g].size() - 1;
while( l < r )
{
int m = ( l + r )/2;
if( testNode( g , m ) ) r = m;
else l = m + 1;
}
return groups[g][r];
}
void find_pair(int N, vector<int> u, vector<int> v, int a, int b)
{
A = a; B = b;
n = N; m = (int)u.size();
for(int i = 0 ; i < m ; i++)
U[i] = u[i], V[i] = v[i];
groups.push_back( vector<int>() );
for(int i = 0 ; i < n ; i++)
groups[0].push_back( i );
divideGroups();
int groupS = bsGroup();
int groupT = groupS + 1;
for(int i = 0 ; i < (int)groups.size() ; i++)
paintGroup( groups[i] , 0 );
paintGroup( groups[groupT] , 1 );
int S = bsNode( groupS );
paintGroup( groups[groupS] , 0 );
paintGroup( groups[groupT] , 0 );
color[S] = 1;
int T = bsNode( groupT );
answer( S , T );
}
