#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int p;
vector<pair<node*, int>> l;
int d, id;
};
void dfs(node* n, node* p, int d){
n->d = d;
for(auto [c,x] : n->l){
if(c==p) continue;
c->p = x;
dfs(c, n, d+1);
}
}
void zfs(node* n, node* p, vector<node*>& o){
for(auto [c,x] : n->l){
if(c!=p) zfs(c, n, o);
}
o.push_back(n);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
node g[N];
int m = U.size();
bool tsub = true;
for(int i = 0;i < U.size();i++){
tsub &= U[i]==i && V[i]==i+1;
g[U[i]].l.emplace_back(&g[V[i]], i);
g[V[i]].l.emplace_back(&g[U[i]], i);
}
for(int i = 0;i < N;i++) g[i].id = i;
vector<int> w(m, 0);vector<node*> o;
zfs(&g[0], NULL, o);
long long dis = ask(w)/A;
int l = 0, r = N-1, mid;
while(l<r){
mid=l+r>>1;
for(int i = l;i <= mid;i++){
for(auto [c,x] : o[i]->l) w[x]=1;
}
long long re = ask(w);
for(int i = l;i <= mid;i++){
for(auto [c,x] : o[i]->l) w[x]=0;
}
if(re>dis*A){
r = mid;
} else {
l=mid+1;
}
}
int s = o[l]->id;
dfs(o[l], NULL, 0);
vector<pair<int, int>> v;
for(int i = 0;i < N;i++) if(g[i].d == dis) v.emplace_back(g[i].p, i);
l = 0; r = v.size()-1;
while(l<r){
mid = l+r>>1;
for(int i = l;i <= mid;i++) w[v[i].first] = 1;
long long re = ask(w);
for(int i = l;i <= mid;i++) w[v[i].first] = 0;
if(re > dis*A){
r = mid;
} else l = mid+1;
}
answer(s, v[l].second);
}
