#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
vector<vector<array<int, 2>>> v(N);
for(int i=0;i<M;i++) {
v[U[i]].push_back({V[i], i});
v[V[i]].push_back({U[i], i});
}
auto query = [&](vector<array<int, 2>> L) {
vector<int> w(M, 0);
for(auto [d, u] : L) for(auto [x, id] : v[u]) w[id] = 1;
return ask(w);
};
auto bfs = [&](int s) -> vector<int> {
vector<int> d(N, -1);
queue<int> q;
q.push(s), d[s] = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
for(auto [x, id] : v[u]) {
if(d[x] == -1) q.push(x), d[x] = d[u]+1;
}
}
return d;
};
ll D = query({});
auto find_deepest = [&](int s, vector<int> e) {
auto d = bfs(s);
vector<array<int, 2>> L;
for(auto x : e) L.push_back({d[x], x});
sort(L.rbegin(), L.rend());
int l = 1, r = (int)L.size()-1;
while(l <= r) {
int mid = (l+r) >> 1;
if(query(vector<array<int, 2>>(L.begin(), L.begin()+mid)) == D) l = mid+1;
else r = mid-1;
}
return L[r][1];
};
int l = 1, r = M-1;
while(l <= r) {
int mid = (l+r) >> 1;
vector<int> w(M, 0);
fill(w.begin(), w.begin()+mid+1, 1);
if(ask(w) == D) l = mid+1;
else r = mid-1;
}
int S = U[r], T = V[r];
vector<int> d[2] = {bfs(S), bfs(T)}, e[2];
for(int i=0;i<N;i++) e[d[0][i] > d[1][i]].push_back(i);
int ans[2] = {-1, -1};
for(int i=0;i<2;i++) ans[i] = find_deepest(i?T:S, e[i]);
answer(ans[0], ans[1]);
}
