#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(vector<pair<int, int>> st, vector<vector<int>> &edge, int m, int base){
vector<signed> w(m, 0);
int l = 0, r = 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, b = (int)bp;
int m = 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;
}
r--;
vector<vector<pair<int, int>>> adj(n);
for(int i = r; 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);
vector<int> vis(n, 0);
queue<pair<int, int>> q;
int st1 = u[r];
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[r];
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>> s1, s2;
for(int i = 0; i < n; i++){
if(dist[i] < dist2[i]) s1.push_back({dist[i],i});
else if(dist[i] > dist2[i]) s2.push_back({dist2[i],i});
}
sort(s1.begin(), s1.end(), greater<>());
sort(s2.begin(), s2.end(), greater<>());
vector<vector<int>> edgeL, edgeR;
for(int i = 0; i < s1.size()-1; i++){
vector<int> pb;
int x = s1[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 < s2.size()-1; i++){
vector<int> pb;
int x = s2[i].se;
for(auto [nx, id]: adj[x])
if(dist2[x] > dist2[nx]) pb.push_back(id);
edgeR.push_back(pb);
}
answer(sub2(s1, edgeL, m, base), sub2(s2, edgeR, m, base));
}
