#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll query(int M, vector<int> L) {
vector<int> w(M, 0);
for(auto x : L) w[x] = 1;
return ask(w);
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
vector<int> d(N, 0), p(N, 0);
ll D = query(M, {});
vector<vector<array<int, 2>>> v(N);
for(int i=0;i<M;i++) {
v[U[i]].push_back({V[i], i});
v[V[i]].push_back({U[i], i});
}
queue<int> q;
q.push(0), d[0] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
for(auto [x, id] : v[u]) if(!d[x]) q.push(x), d[x] = d[u]+1, p[x] = id;
}
vector<int> L, P;
for(int i=0;i<N;i++) if(d[i] == D/A+1) L.push_back(i), P.push_back(p[i]);
int l = 0, r = (int)L.size()-1;
while(l <= r) {
int mid = (l+r) >> 1;
if(query(M, vector<int>(P.begin(), P.begin()+mid)) >= D) r = mid-1;
else l = mid+1;
}
answer(0, L[l]);
}
