#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
vector <pair<ll, ll>> adj[N+5];
for (int i=0; i<M; i++) {
adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i});
}
vector <int> W(M), dist(N, 1e9), par(N);
ll z = ask(W)/A;
queue <ll> q;
dist[0] = 0;
q.push(0);
vector <ll> v;
while (!q.empty()) {
auto idx = q.front(); q.pop();
v.push_back(idx);
for (auto [i, j] : adj[idx]) {
if (dist[i]>dist[idx]+1) {
dist[i] = dist[idx]+1;
par[i] = j;
q.push(i);
}
}
}
sort(v.begin(), v.end(), [&](ll a, ll b) {
return dist[a]>dist[b];
});
ll lf = 0, rg = (ll)v.size()-1, S = -1, T = -1;
ll cur = -1;
while (lf<=rg) {
ll mid = (lf+rg)/2;
while (cur+1<=mid) {
cur++;
W[par[v[cur]]] = 1;
}
while (cur>mid) {
W[par[v[cur]]] = 0;
cur--;
}
if (ask(W) != z*A) {
S = v[mid];
rg = mid-1;
}
else lf = mid+1;
}
for (int i=0; i<N; i++) dist[i] = 1e9;
for (int i=0; i<M; i++) W[i] = 0;
dist[S] = 0;
q.push(S);
v.clear();
while (!q.empty()) {
auto idx = q.front(); q.pop();
if (dist[idx] == z) {
v.push_back(idx);
continue;
}
for (auto [i, j] : adj[idx]) {
if (dist[i]>dist[idx]+1) {
dist[i] = dist[idx]+1;
par[i] = j;
q.push(i);
}
}
}
lf = 0, rg = (ll)v.size()-1;
cur = -1;
while (lf<=rg) {
ll mid = (lf+rg)/2;
while (cur+1<=mid) {
cur++;
W[par[v[cur]]] = 1;
}
while (cur>mid) {
W[par[v[cur]]] = 0;
cur--;
}
if (ask(W) != z*A) {
T = v[mid];
rg = mid-1;
}
else lf = mid+1;
}
answer(S, T);
}
