#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
vector<vector<pii>> adj;
vector<int> d;
vector<pii> par;
void dfs(int x, int p) {
for(pii edge: adj[x]) {
int i = edge.first, idx = edge.second;
if(i==p)continue;
par[i]={x, idx};
d[i]=d[x]+1;
dfs(i,x);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
adj.resize(N);
d.resize(N);
par.resize(N);
int M = U.size();
/*for (int j = 0; j < 50; ++j) {
std::vector<int> w(M);
for (int i = 0; i < M; ++i) {
w[i] = 0;
}
long long toll = ask(w);
}*/
vector<int> query; query.assign(M,0);
ll toll = ask(query);
ll depth = toll/A;
for(int i=0;i<M;i++) {
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
d[0]=0;
par[0]={0,-1};
dfs(0,0);
vector<int> nodes;
for(int i=0;i<N;i++) {
if(d[i]==depth)nodes.push_back(i);
}
int lo=0, hi=nodes.size()-1;
//for(int i=0;i<N;i++) cout<<nodes[i]<<" ";
//cout<<"\n";
while(lo<hi) {
int mid = (lo+hi)/2;
vector<int> query; query.assign(M,0);
//cout<<lo<<" "<<mid<<"\n";
for(int i=lo;i<=mid;i++) {
query[par[nodes[i]].second]=1;
}
ll toll2 = ask(query);
if(toll2 != toll) {
hi=mid;
}
else lo=mid+1;
}
answer(0, nodes[lo]);
}
