#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
vector<vector<ii> > vec;
vector<int> query;
vector<ii> target;
ll dist,a,b;
void dfs(int node,int high,int p){
if(high!=-1)target.pb(ii(high,node));
for(auto child:vec[node])
if(child.fi!=p)
dfs(child.fi,child.se,node);
}
void dfs2(int node,ll d,int high,int p){
if(d*a==dist){
target.pb(ii(high,node));
return;
}
for(auto child:vec[node])
if(child.fi!=p)
dfs2(child.fi,d+1,child.se,node);
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
a=A,b=B;
vec.resize(N);
query.resize(M);
bool subtask=1;
for (int i = 0; i < M; ++i)
{
vec[U[i]].pb(ii(V[i],i));
vec[V[i]].pb(ii(U[i],i));
if(U[i]!=i||V[i]!=i+1)subtask=0;
}
if(subtask){
int start=0;
for (int i = 0; i < N; ++i)
{
if(vec[i].size()==1){
start=i;
break;
}
}
fill(query.begin(),query.end(),0);
dist=ask(query);
dfs(start,-1,0);
//sort(target.begin(),target.end());
int l=0,r=(int)(target.size())-1;
int n1=-1,n2=-1,L=0;
while(l<r){
int med=(l+r)>>1;
L=med;
fill(query.begin(),query.end(),0);
for (int i = l; i <= med; ++i)
query[target[i].fi]=1;
ll check=ask(query);
if(check==dist)
l=med+1;
else if(check==(dist/A)*B){
r=med;
}
else{
ll nb_edges=(check-dist)/(B-A);
//cerr<<l<<" "<<r<<" "<<nb_edges<<" "<<med<<"\n";
n1=(((med-nb_edges)<0)?start:target[med-nb_edges].se);
n2=target[med+(dist-nb_edges*A)/A].se;
//cerr<<n1<<" "<<n2<<"\n";
break;
}
}
if(n1!=-1)
answer(n1, n2);
else
answer((L?target[L-1].se:start),target[L].se);
}
else{
fill(query.begin(),query.end(),0);
dist=ask(query);
dfs2(0,0,-1,0);
sort(target.begin(),target.end());
int l=0,r=(int)target.size()-1,ans=0;
while(l<=r){
int med=(l+r)>>1;
fill(query.begin(),query.end(),0);
for (int i = l; i <= med; ++i)
query[target[i].fi]=1;
ll check=ask(query);
if(check!=dist){
ans=med;
r=med-1;
}
else l=med+1;
}
answer(0, target[ans].se);
}
}
