#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){
return a.size();
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<vector<int>> g;
vector<int> u, v;
int n, m;
vector<int> nodes, ch;
void dfs(int tar, int i, int p = -1, int d = 0){
for(auto j : g[i]){
int x = u[j] ^ v[j] ^ i;
if(x == p) continue;
if(d + 1 == tar){
nodes.push_back(j);
ch.push_back(x);
}else{
dfs(tar, x, i, d + 1);
}
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int a, int b) {
n = N;
u = U;
v = V;
m = len(v);
g.resize(n);
for(int i = 0; i < m; i ++){
g[u[i]].push_back(i);
g[v[i]].push_back(i);
}
vector<int> w(m);
ll d = ask(w) / a;
dfs(d, 0);
int l = -1, r = len(nodes) - 1;
//cout << r << endl;
//for(auto u : ch) cout << u << endl;
while(r - l > 1){
int mid = (l + r) / 2;
for(int i = 0; i <= mid; i ++){
w[nodes[i]] = 1;
}
for(int i = mid + 1; i < len(nodes); i ++){
w[nodes[i]] = 0;
}
if(ask(w) != d * a){
r = mid;
}else l = mid;
}
//cout << r << endl;
answer(0, ch[r]);
}
