#include "bits/stdc++.h"
#include "highway.h"
using namespace std;
const int maxn = 1e5;
vector <int> g[maxn];
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
int m = U.size();
int l, r;
long long initDist = ask(vector <int> (m, 0));
l = 0, r = m;
while(l < r) {
vector <int> v (m, 0);
int mid = (l + r + 1) >> 1;
for(int i = 0; i < mid; i++) {
v[i] = 1;
}
if(ask(v) == initDist) {
l = mid;
} else {
r = mid - 1;
}
}
vector <int> state (m, 0);
for(int i = 0; i < l; i++) state[i] = 1;
vector <int> order;
queue <int> Q;
vector <int> dist (n, -1);
Q.push(U[l]);
Q.push(V[l]);
dist[U[l]] = dist[V[l]] = 0;
for(int i = 0; i < m; i++) {
if(state[i] == 0) {
g[U[i]].push_back(V[i]);
g[V[i]].push_back(U[i]);
}
}
while(not Q.empty()) {
int x = Q.front();
Q.pop();
order.push_back(x);
for(int i : g[x]) {
if(dist[i] == -1) {
dist[i] = dist[x] + 1;
Q.push(i);
}
}
}
reverse(order.begin(), order.end());
auto getEndpoint = [&] (vector <int> order) {
int l = 0, r = n - 1;
while(l < r) {
int mid = (l + r) >> 1;
vector <int> v = state;
vector <int> mark (n, 0);
for(int i = 0; i <= mid; i++) {
mark[order[i]] = 1;
}
for(int i = 0; i < m; i++) {
if(mark[U[i]] || mark[V[i]]) {
v[i] = 1;
}
}
if(ask(v) == initDist) {
l = mid + 1;
} else {
r = mid;
}
}
return order[l];
};
int src = getEndpoint(order);
Q.push(src);
dist = vector <int> (n, -1);
dist[src] = 0;
order.clear();
while(not Q.empty()) {
int x = Q.front();
Q.pop();
order.push_back(x);
for(int i : g[x]) {
if(dist[i] == -1) {
dist[i] = 1 + dist[x];
Q.push(i);
}
}
}
reverse(order.begin(), order.end());
int des = getEndpoint(order);
answer(src, des);
}
