#include "highway.h"
#include <queue>
#include <algorithm>
#define int long long
#define fi first
#define se second
#define ll int
using namespace std;
int sub2(const vector<pair<int,int>> &st, const vector<vector<int>> &edge, int m, int base){
if (st.empty()) return -1;
if (st.size() == 1) return st[0].se;
vector<signed> w(m, 0);
int l = 0, r = (int)st.size() - 1;
while (l < r){
int mid = (l + r) / 2;
fill(w.begin(), w.end(), 0);
for (int i = 0; i <= mid; i++){
for (int id : edge[i]){
w[id] = 1;
}
}
if (ask(w) > base) r = mid;
else l = mid + 1;
}
return st[r].se;
}
void find_pair(signed n, vector<signed> u, vector<signed> v, signed ap, signed bp) {
int a = (int)ap;
int m = (int)u.size();
vector<signed> w(m, 0);
int base = ask(w);
int len = base / a;
int l = 1, r = m;
while (l < r){
int mid = (l + r) / 2;
fill(w.begin(), w.end(), 0);
for (int i = 0; i < mid; i++) w[i] = 1;
if (ask(w) > len * a) r = mid;
else l = mid + 1;
}
int chosen = r - 1;
vector<vector<pair<int,int>>> adj(n);
for (int i = chosen; i < m; i++){
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
vector<int> dist(n, -1), dist2(n, -1), vis(n, 0);
queue<pair<int,int>> q;
int st1 = u[chosen];
q.push({st1, 0});
vis[st1] = 1;
while (!q.empty()){
auto [x, d] = q.front();
q.pop();
dist[x] = d;
for (auto [nx, id] : adj[x]){
if (vis[nx]) continue;
vis[nx] = 1;
q.push({nx, d + 1});
}
}
fill(vis.begin(), vis.end(), 0);
int st2 = v[chosen];
q.push({st2, 0});
vis[st2] = 1;
while (!q.empty()){
auto [x, d] = q.front();
q.pop();
dist2[x] = d;
for (auto [nx, id] : adj[x]){
if (vis[nx]) continue;
vis[nx] = 1;
q.push({nx, d + 1});
}
}
vector<pair<int,int>> left, right;
for (int i = 0; i < n; i++){
if (dist[i] < dist2[i]) left.push_back({dist[i], i});
else right.push_back({dist2[i], i}); // ties go here
}
sort(left.begin(), left.end(), greater<>());
sort(right.begin(), right.end(), greater<>());
vector<vector<int>> edgeL, edgeR;
for (int i = 0; i + 1 < (int)left.size(); i++){
vector<int> pb;
int x = left[i].se;
for (auto [nx, id] : adj[x]){
if (dist[x] > dist[nx]) pb.push_back(id);
}
edgeL.push_back(pb);
}
for (int i = 0; i + 1 < (int)right.size(); i++){
vector<int> pb;
int x = right[i].se;
for (auto [nx, id] : adj[x]){
if (dist2[x] > dist2[nx]) pb.push_back(id);
}
edgeR.push_back(pb);
}
answer(sub2(left, edgeL, m, base), sub2(right, edgeR, m, base));
}
