#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int n, M;
long long ori;
vector<pii> adj[90009];
vector<int> u, v;
int D[90009];
pii ebs() {
int l = 0, r = M-1;
while(l <= r) {
if(l == r) return (pii){u[l], v[l]};
int m = l+r >> 1;
vector<int> W(M, 0);
for(int i=0; i<=m; i++) W[i] = 1;
if(ask(W) != ori) r = m;
else l = m+1;
}
return (pii){u[r+1], v[r+1]};
}
int vbs(vector<int> S) {
int K = S.size();
int l = 0, r = K-1;
while(l <= r) {
if(l == r) return S[l];
int m = l+r >> 1;
vector<int> W(M, 0);
for(int i=0; i<=m; i++) for(auto& it: adj[S[i]]) W[it.second] = 1;
if(ask(W) != ori) r = m;
else l = m+1;
}
return S[r+1];
}
vector<int> f(vector<int>& D, int root) {
int c = 1;
for(int i=0; i<n; i++) D[i] = 0;
queue<int> que; que.push(root); D[root] = 1;
while(que.size()) {
int sz = que.size();
while(sz--) {
int now; now = que.front(); que.pop();
for(auto& it: adj[now]) {
if(!D[it.first]) {
D[it.first] = c+1;
que.push(it.first);
}
}
}
++c;
}
vector<int> S;
for(int i=0; i<n; i++) S.push_back(i);
sort(S.begin(), S.end(), [&](int P, int Q) {return D[P] > D[Q];});
return S;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
u = U; v = V;
n = N; M = U.size();
for(int i=0; i<M; i++) {
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
vector<int> W(M, 0); ori = ask(W);
int al, be; tie(al, be) = ebs();
vector<int> DA(N), DB(N);
f(DA, al); f(DB, be);
vector<int> AS, BS, CS;
for(int i=0; i<N; i++) {
if(DA[i] < DB[i]) AS.push_back(i);
else BS.push_back(i);
}
sort(AS.begin(), AS.end(), [&](int X, int Y) {return DA[X] > DA[Y];});
int P = vbs(AS);
for(auto& it: BS) if(DB[it] == (ori / A) - DA[P] + 1) CS.push_back(it);
sort(CS.begin(), CS.end(), [&](int X, int Y) {return DB[X] > DB[Y];});
int Q = vbs(CS);
answer(P, Q);
}
