#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 9e4 + 20;
vector<pair<int, int>> adj[maxN];
bool flag[maxN];
int distX[maxN];
int distY[maxN];
long long min_dist;
int N, M;
void bfs1(int X, int distX[]) {
for (int i = 0; i < N; i++) {
flag[i] = false;
}
deque<int> q = {X};
flag[X] = true;
distX[X] = 0;
while (!q.empty()) {
int u = q.front();
q.pop_front();
for (auto e: adj[u]) {
int v = e.first;
if (!flag[v]) {
flag[v] = true;
distX[v] = distX[u] + 1;
q.push_back(v);
}
}
}
}
vector<pair<int, int>> bfs2(int X, int distX[], int distY[]) {
for (int i = 0; i < N; i++) {
flag[i] = false;
}
deque<int> q = {X};
flag[X] = true;
vector<pair<int, int>> tree;
while (!q.empty()) {
int u = q.front();
q.pop_front();
for (auto e: adj[u]) {
int v = e.first;
int id = e.second;
if (distX[v] < distY[v] && !flag[v]) {
flag[v] = true;
q.push_back(v);
tree.emplace_back(v, id);
}
}
}
return tree;
}
int solve(int X, vector<pair<int, int>> treeX, vector<pair<int, int>> treeY) {
int sz = treeX.size();
int lt = 0;
int rt = sz - 1;
int res = X;
while (lt <= rt) {
int mt = (lt + rt) / 2;
vector<int> heavy(M, 1);
for (auto p: treeY) {
heavy[p.second] = 0;
}
for (int i = mt + 1; i < sz; i++) {
heavy[treeX[i].second] = 0;
}
if (ask(heavy) != min_dist) {
res = treeX[mt].first;
rt = mt - 1;
}
else {
lt = mt + 1;
}
}
return res;
}
void find_pair(int _N, vector<int> U, vector<int> V, int A, int B) {
N = _N;
M = U.size();
for (int i = 0; i < M; i++) {
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
min_dist = ask(vector<int>(M, 0));
int lt = 0;
int rt = M - 1;
int X = -1;
int Y = -1;
while (lt <= rt) {
int mt = (lt + rt) / 2;
vector<int> heavy(M);
for (int i = 0; i <= mt; i++) {
heavy[i] = 1;
}
if (ask(heavy) != min_dist) {
X = U[mt];
Y = V[mt];
rt = mt - 1;
}
else {
lt = mt + 1;
}
}
bfs1(X, distX);
bfs1(Y, distY);
vector<pair<int, int>> treeX = bfs2(X, distX, distY);
vector<pair<int, int>> treeY = bfs2(Y, distY, distX);
reverse(treeX.begin(), treeX.end());
reverse(treeY.begin(), treeY.end());
answer(solve(X, treeX, treeY), solve(Y, treeY, treeX));
}
