#include "highway.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7;
void find_pair(int n, vi _u, vi _v, int a, int b) {
V<vi> G(n), g(n);
int m = SZ(_u);
for(int i = 0; i < m; i++) {
int u = _u[i], v = _v[i];
G[u].PB(v);
G[v].PB(u);
g[u].PB(i);
g[v].PB(i);
}
auto qry = [&] (vi s) -> ll {
vi w(m);
for(int i:s)
w[i] = 1;
return ask(w);
};
ll he = qry(vi());
int lb = 0, rb = m - 1;
while(lb <= rb) {
int mb = (lb + rb) / 2;
vi bad(mb + 1); iota(ALL(bad), 0);
if(qry(bad) != he) rb = mb - 1;
else lb = mb + 1;
}
auto BFS = [&] (int s) {
vi d(n, -1);
d[s] = 0;
queue<int> q({s});
while(q.size()) {
int u = q.front(); q.pop();
for(int v:G[u]) if(d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
}
return d;
};
int u = _u[lb], v = _v[lb];
vi du = BFS(u), dv = BFS(v);
vi s, t;
for(int i = 0; i < n; i++) {
if(du[i] < dv[i]) {
s.PB(i);
} else if(du[i] > dv[i]) {
t.PB(i);
}
}
sort(ALL(s), [&] (int i, int j) {
return du[i] > du[j];
});
sort(ALL(t), [&] (int i, int j) {
return dv[i] > dv[j];
});
lb = 0, rb = SZ(s) - 1;
while(lb <= rb) {
int mb = (lb + rb) / 2;
vi bad;
for(int i = 0; i <= mb; i++)
for(int e:g[s[i]])
bad.PB(e);
if(qry(bad) != he) rb = mb - 1;
else lb = mb + 1;
}
int S = s[lb];
lb = 0, rb = SZ(t) - 1;
while(lb <= rb) {
int mb = (lb + rb) / 2;
vi bad;
for(int i = 0; i <= mb; i++)
for(int e:g[t[i]])
bad.PB(e);
if(qry(bad) != he) rb = mb - 1;
else lb = mb + 1;
}
int T = t[lb];
answer(S, T);
}
