#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
const int mx = 90005;
int N, M;
ll A, B;
int D;
vi U, V;
vpi adj[mx]; //node, edge
int getDist(){
vi w(M, 0);
return ask(w)/A;
}
vpi jeds; //edges just before degree d nodes, label of nodes
void findJeds(int node, int d = 0, int prv = -1){
for(auto u: adj[node]){
if(u.f == prv) continue;
if(d+1 == D){
jeds.pb(mp(u.s, u.f));
continue;
}
findJeds(u.f, d+1, node);
}
}
void find_pair(int _N, vi _U, vi _V, int _A, int _B) {
N = _N;
U = _U;
V = _V;
M = sz(U);
for(int i = 0; i < M; i++){
adj[U[i]].pb(mp(V[i], i));
adj[V[i]].pb(mp(U[i], i));
}
A = _A;
B = _B;
if(M == N-1){ //TREE CASE
bool isLine = 1;
for(int i = 0; i < M; i++){
if(U[i] != i || V[i] != i+1) isLine = 0;
}
if(isLine){
D = getDist();
vi sts;
for(int i = 0; i < N; i++){
if(i+D < N) sts.pb(i);
}
while(sz(sts) > 1){
vi nsts;
vi osts;
for(int i = 0; i < sz(sts)/2; i++){
nsts.pb(sts[i]);
}
for(int i = sz(sts)/2; i < sz(sts); i++){
osts.pb(sts[i]);
}
vi w(M, 0);
for(auto u: nsts) w[u] = 1;
if(ask(w) == A*D){
sts = osts;
}
else sts = nsts;
}
answer(sts[0], sts[0]+D);
return;
}
D = getDist();
findJeds(0, 0);
while(sz(jeds) > 1){
vpi njeds;
vpi ojeds;
for(int i = 0; i < sz(jeds)/2; i++){
njeds.pb(jeds[i]);
}
for(int i = sz(jeds)/2; i < sz(jeds); i++){
ojeds.pb(jeds[i]);
}
vi w(M, 0);
for(auto u: njeds){
w[u.f] = 1;
}
if(ask(w) == A*D){
jeds = ojeds;
}
else jeds = njeds;
}
answer(0, jeds[0].s);
return;
}
}
