#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e5 + 3e2;
int N;
vector<pair<int, int>> g[MAXN];
void bfs(int root, vector<int> &d, vector<int> &edges, vector<int> &p){
queue<int> q;
vector<bool> used(N, false);
used[root] = true;
q.push(root);
d[root] = 0;
p[root] = -1;
while (!q.empty()){
int x = q.front(); q.pop();
for (auto e : g[x]){
int y = e.first, i = e.second;
if (!used[y]){
used[y] = true;
q.push(y);
d[y] = d[x] + 1;
p[y] = i;
edges.push_back(i);
}
}
}
}
vector<int> vec;
void find_pair(int _N, vector<int> U, vector<int> V, int A, int B) {
N = _N;
int M = U.size();
for (int i = 0; i < M; i++){
g[U[i]].emplace_back(V[i], i);
g[V[i]].emplace_back(U[i], i);
}
vector<int> w(M, 0);
ll onlyA = ask(w);
int ind = 0;
int l = 0, r = M - 1;
while (l <= r){
int mid = (l + r) >> 1;
fill(all(w), 0);
for (int i = 0; i <= mid; i++) w[i] = 1;
ll res = ask(w);
if (res != onlyA){
ind = mid;
r = mid - 1;
} else l = mid + 1;
}
int u = U[ind], v = V[ind];
// cerr << u << ' ' << v << endl;
vector<int> du(N), dv(N), pu(N), pv(N);
vector<int> eu, ev;
bfs(u, du, eu, pu);
bfs(v, dv, ev, pv);
pu[u] = pv[v] = ind;
for (int i = 0; i < g[U[ind]].size(); i++){
if (g[U[ind]][i].first == V[ind]) g[U[ind]].erase(g[U[ind]].begin() + i);
}
for (int i = 0; i < g[V[ind]].size(); i++){
if (g[V[ind]][i].first == U[ind]) g[V[ind]].erase(g[V[ind]].begin() + i);
}
vector<int> a, b;
for (int i = 0; i < N; i++){
if (du[i] < dv[i]) a.push_back(i);
if (dv[i] < du[i]) b.push_back(i);
}
sort(all(a), [&](int i, int j){
return du[i] < du[j];
});
sort(all(b), [&](int i, int j){
return dv[i] < dv[j];
});
// cerr << endl;
// for (int x : a) cerr << x << ' ' << pu[x] << endl; cerr << endl;
// for (int x : b) cerr << x << ' ' << pv[x] << endl; cerr << endl;
int S = -1, T = -1;
l = 0, r = a.size() - 1;
while (l <= r){
int mid = (l + r) >> 1;
fill(all(w), 1);
w[ind] = 0;
for (int i = 0; i <= mid; i++) w[pu[a[i]]] = 0;
for (int i : b) w[pv[i]] = 0;
if (ask(w) == onlyA){
S = a[mid];
r = mid - 1;
} else l = mid + 1;
}
l = 0, r = b.size() - 1;
while (l <= r){
int mid = (l + r) >> 1;
fill(all(w), 1);
w[ind] = 0;
for (int i = 0; i <= mid; i++) w[pv[b[i]]] = 0;
for (int i : a) w[pu[i]] = 0;
// cerr << "mid = " << mid << endl;
// for (int x : w) cerr << x << ' '; cerr << endl << endl;
if (ask(w) == onlyA){
T = b[mid];
r = mid - 1;
} else l = mid + 1;
}
// cerr << S << ' ' << T << endl;
answer(S, T);
}
