#include "highway.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define ll long long
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pii pair<int,int>
#define mk make_pair
#define all(x) x.begin(),x.end()
#define pb push_back
const int MAX = 90010 ;
using namespace std ;
int N , A , B , M ;
int group[MAX] ;
vector<int> toAsk ;
vector<pii> adj[MAX] ;
int dist[2][MAX] ;
long long C ;
vector<int> ans ;
void bfsDist(int S, int idx )
{
for(int i = 0 ; i < N ; i++ ) dist[idx][i] = M+10 ;
dist[idx][S] = 0 ;
vector<int> fila = {S} ;
int ini = 0 ;
while(ini < sz(fila))
{
int x = fila[ini++] ;
for(auto e : adj[x])
{
if(dist[idx][e.ff] <= dist[idx][x]+1 ) continue ;
dist[idx][e.ff] = dist[idx][x]+1 ;
fila.pb(e.ff) ;
}
}
}
void bfs(int S, int idx )
{
vector<int> fila = {S} , edge ;
int ini = 0 ;
group[S] = -1 ;
while(ini < sz(fila))
{
int x = fila[ini++] ;
for(auto e : adj[x] )
{
if(group[e.ff] != idx ) continue ;
group[e.ff] = -1 ;
fila.pb(e.ff) ;
edge.pb(e.ss) ;
}
}
int l = 0 , r = sz(edge)-1 , mid , best = -1;
while(l <= r )
{
mid = (l+r)>>1 ;
lp(i,0,M) toAsk[i] = 1 ;
for(auto e : edge ) toAsk[e] = 0 ;
for(int i = 0 ; i <= mid ; i++ ) toAsk[ edge[i] ] = 1 ;
ll c = ask(toAsk) ;
if( c == (C/A)*(ll)B )
{
r = mid-1 ;
best = mid ;
}
else l = mid+1 ;
}
ans.pb(fila[best+1]) ;
}
void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B)
{
N = _N ;
A = _A ;
B = _B ;
M = sz(U) ;
for(int i = 0 ; i < M ; i++ )
for(int j = 0 ; j < 2 ; j++ , swap(U[i] , V[i]))
adj[U[i]].pb( mk(V[i],i) ) ;
lp(i,0,M) toAsk.pb(0) ;
C = ask(toAsk);
int l = 0 , r = sz(U)-1 , mid , best = 0 ;
while(l <= r )
{
mid = (l+r)>>1 ;
for(int i = 0 ; i <= mid ; i++ ) toAsk[i] = 1 ;
for(int i = mid+1 ; i < M ; i++ ) toAsk[i] = 0 ;
if(ask(toAsk) != C )
{
best = mid ;
r = mid-1 ;
}
else l = mid+1 ;
}
bfsDist( U[best] , 0 ) ;
bfsDist( V[best] , 1 ) ;
for(int i = 0 ; i < N ; i++ )
{
if( dist[0][i] == dist[1][i] ) group[i] = -1 ;
else if( dist[0][i] > dist[1][i] ) group[i] = 1 ;
}
bfs(U[best] , 0 ) ;
bfs(V[best] , 1 ) ;
answer(ans[0] , ans[1]) ;
}
