#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 4e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
vector<vector<pii>> edges(N);
int M = sz(U);
for(int i = 0; i < M; i++)
edges[U[i]].pb({V[i], i}), edges[V[i]].pb({U[i], i});
vector<int> dist(N), ord_edges;
queue<int> fila;
fila.push(0);
while(!fila.empty()) {
int x = fila.front();
fila.pop();
for(auto [viz, ind] : edges[x]) {
if(dist[viz] == 0 and viz != 0) {
dist[viz] = dist[x] + 1;
ord_edges.pb(ind);
fila.push(viz);
}
}
}
vector<int> query(M);
ll def = ask(query);
int l = 0, r = N-1;
while(l < r) {
int mid = (l+r)/2;
for(int i = 0; i <= mid; i++) query[ord_edges[i]] = 0;
for(int i = mid+1; i < N-1; i++) query[ord_edges[i]] = 1;
if(ask(query) > def) l = mid+1;
else r = mid;
}
int k = ord_edges[l], S;
if(dist[U[k]] > dist[V[k]]) S = U[k];
else S = V[k];
ord_edges.clear();
fila.push(S);
dist.clear();
dist.resize(N,0);
while(!fila.empty()) {
int x = fila.front();
fila.pop();
for(auto [viz, ind] : edges[x]) {
if(dist[viz] == 0 and viz != S) {
dist[viz] = dist[x] + 1;
ord_edges.pb(ind);
fila.push(viz);
}
}
}
query.clear();
query.resize(M,0);
l = 0;
r = N-1;
while(l < r) {
int mid = (l+r)/2;
for(int i = 0; i <= mid; i++) query[ord_edges[i]] = 0;
for(int i = mid+1; i < N-1; i++) query[ord_edges[i]] = 1;
if(ask(query) > def) l = mid+1;
else r = mid;
}
k = ord_edges[l];
int T = V[k];
if(dist[U[k]] > dist[V[k]]) T = U[k];
answer(S,T);
}
