#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define ll long long int
#define pii pair<int,int>
const int N = 2e5+100;
vector<pii> g[N];
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
int m = U.size();
for(int i = 0; i < m; ++i){
g[U[i]].pb({V[i], i});
g[V[i]].pb({U[i], i});
}
vi w(m);
ll val = ask(w);
int k = val / A;
vector<bool> vis(n);
queue<int> q;
vi dist(n);
q.push(0);
vis[0] = 1;
vi T, par(n);
while(!q.empty()){
int v = q.front(); q.pop();
if(dist[v] == k) T.pb(v);
for(auto [u, id]: g[v]){
if(!vis[u]){
par[u] = id;
dist[u] = dist[v] + 1;
q.push(u);
vis[u] = 1;
}
}
}
int l = 0, r = int(T.size()) - 2, res = int(T.size())-1;
while(l <= r){
int mid = l+r>>1;
w.clear();
w.resize(m, 0);
for(int i = 0; i <= mid; ++i) w[par[T[i]]] = 1;
if(ask(w) > val){
res = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
answer(0, T[res]);
}
