#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using ll = long long;
const int N = 90090;
vector<pair<int, int>> adj[N], e;
int n;
int p[N], sz[N];
int fr(int i) {
return (p[i] == i) ? i : p[i] = fr(p[i]);
}
void dfs(int v, int p = -1) {
for (auto& x : adj[v]) {
if (x.first == p) continue;
e.push_back({ x.second, x.first });
dfs(x.first, v);
}
}
void find_pair(int NN, vector<int> U, vector<int> V, int A, int B) {
n = NN;
int m = U.size();
for (int i = 0;i < n;i++) p[i] = i;
for (int i = 0;i < m;i++) {
int u = U[i], v = V[i];
int pu = fr(u), pv = fr(v);
if (pu != pv) {
adj[u].push_back({ v,i });
adj[v].push_back({ u,i });
p[pu] = pv;
}
}
vector<int> QQ(m, 0);
ll mnp = ask(QQ);
dfs(0);
int l = 1, r = n - 1;
while (l < r) {
int mid = (l + r) / 2;
vector<int> q(m, 1);
for (int i = 0;i < mid;i++) {
q[e[i].first] = 0;
}
if (ask(q) == mnp) r = mid;
else l = mid + 1;
}
int city2 = e[l - 1].second;
e.clear();
dfs(city2);
l = 1, r = n - 1;
while (l < r) {
int mid = (l + r) / 2;
vector<int> q(m, 1);
for (int i = 0;i < mid;i++) {
q[e[i].first] = 0;
}
if (ask(q) == mnp) r = mid;
else l = mid + 1;
}
int city1 = e[l - 1].second;
answer(city1, city2);
}
