#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using ll = long long;
void find_pair(int n, vector<int> A, vector<int> B, int a, int b) {
//I am so stupid, my binary search was wrong qwq
int m = (int) B.size();
const ll val = ask(vector<int>(m));
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; ++i) {
g[A[i]].push_back({B[i], i});
g[B[i]].push_back({A[i], i});
}
int low = 0, high = m;
while (low + 1 < high) {
int mid = (low + high) >> 1;
vector<int> now(m, 1);
fill(now.begin(), now.begin() + mid, 0);
if (ask(now) == val) {
high = mid;
} else {
low = mid;
}
}
int e = low;
int u = A[e], v = B[e];
vector<int> S, T, root(n), dep(n, -1), par(n, -1);
queue<int> q;
q.push(root[u] = u), q.push(root[v] = v);
par[u] = par[v] = e;
dep[u] = dep[v] = 0;
S.push_back(u), T.push_back(v);
while (!q.empty()) {
int x = q.front();
q.pop();
for (auto [to, i]: g[x]) {
if (dep[to] == -1) {
dep[to] = dep[x] + 1;
root[to] = root[x];
par[to] = i;
q.push(to);
if (root[to] == u) {
S.push_back(to);
} else {
T.push_back(to);
}
}
}
}
auto solve = [&](const vector<int> &t1, const vector<int> &t2) {
int l = 0, r = (int) t1.size();
while (l + 1 < r) {
int mid = (l + r) >> 1;
vector<int> now(m, 1);
for (int x : t2) {
now[par[x]] = 0;
}
for (int i = 0; i < mid; ++i) {
now[par[t1[i]]] = 0;
}
if (ask(now) == val) {
r = mid;
} else {
l = mid;
}
}
return t1[l];
};
answer(solve(S, T), solve(T, S));
}
