#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void dfs(int node, int parent, vector<vector<pair<int, int>>> &adj, vector<int>& depths, vector<pair<int, int>> &sameDepths, int dist){
for(auto [v, i] : adj[node]){
if(v == parent) continue;
depths[v] = depths[node] + 1;
if(depths[v] == dist){
sameDepths.push_back({v, i});
continue;
}
dfs(v, node, adj, depths, sameDepths, dist);
}
}
int bSearch(vector<pair<int, int>>& sameDepths, int M, int dist, ll cost){
int l = 0; int r = sameDepths.size();
vector<int> w(M, 0);
while(l < r){
int mid = (l + r) / 2;
for(int i = l; i <= mid; i++){
w[sameDepths[i].second] = 1;
}
ll newDist = ask(w);
if(newDist == cost){
l = mid + 1;
}else{
for(int i = mid; i < r; i++){
w[sameDepths[i].second] = 0;
}
r = mid;
}
}
return sameDepths[l].first;
}
pair<int, int> search(int N, vector<int> U, vector<int> V, int A, int B){
int M = U.size();
vector<int> initial(M, 0);
ll initialCost = ask(initial);
int distance = initialCost / A;
vector<vector<pair<int, int>>> adj;
for(int i = 0; i < M; i++){
int u = U[i]; int v = V[i];
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
vector<int> depths(M, 0);
vector<pair<int, int>> sameDepth;
dfs(0, 0, adj, depths, sameDepth, distance);
int secondLocation = bSearch(sameDepth, M, distance, initialCost);
return {0, secondLocation};
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
pair<int, int> ans = search(N, U, V, A, B);
answer(ans.first, ans.second);
}
// #include "grader.cpp"
// #include "grader.cpp"
