#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
ll A, B;
int ex[130002], ey[130002];
vector<pair<int, int> > link[100002];
ll def;
int U, V;
void findOneEdge(){
int L = 0, R = m-2, ANS = m-1;
while(L<=R){
int MID = (L+R)/2;
vector<int> tv (m, 0);
for(int i=0; i<=MID; i++) tv[i] = 1;
if(ask(tv) != def) ANS = MID, R = MID-1;
else L = MID+1;
}
U = ex[ANS], V = ey[ANS];
}
int uDist[100002], vDist[100002];
void bfs(int st, int *dist){
queue<pair<int, int> > que;
vector<bool> vec (n);
que.push(make_pair(st, 0));
vec[st] = 1;
while(!que.empty()){
pair<int, int> tmp = que.front(); que.pop();
dist[tmp.first] = tmp.second;
for(auto y: link[tmp.first]){
if(vec[y.first]) continue;
vec[y.first] = 1;
que.push(make_pair(y.first, tmp.second+1));
}
}
}
int group[100002]; /// 1이면 U그룹, 2이면 V그룹
vector<int> base;
vector<int> uVec, vVec;
int uIdx[100002], vIdx[100002];
void binarySearch(int &X, vector<int> &vec, int *idx, int gnum){
int sz = (int)vec.size();
int L = 0, R = sz-2, ANS = sz-1;
while(L<=R){
int MID = (L+R)/2;
vector<int> v = base;
for(int i=0; i<m; i++){
if(group[ex[i]] == gnum && group[ey[i]] == gnum && ((idx[ex[i]] <= i) ^ (idx[ey[i]] <= i))) v[i] = 1;
}
if(ask(v) != def) L = MID+1;
else ANS = MID, R = MID-1;
}
X = vec[ANS];
}
void find_pair(int N, vector<int> _U, vector<int> _V, int _A, int _B){
n = N;
m = (int)_U.size();
def = ask(vector<int> (m, 0));
for(int i=0; i<m; i++){
ex[i] = _U[i], ey[i] = _V[i];
link[ex[i]].push_back(make_pair(ey[i], i));
link[ey[i]].push_back(make_pair(ex[i], i));
}
A = _A, B = _B;
findOneEdge();
bfs(U, uDist);
bfs(V, vDist);
for(int i=0; i<n; i++){
if(uDist[i] == vDist[i]) continue;
if(uDist[i] < vDist[i]) group[i] = 1;
else group[i] = 2;
}
base = vector<int> (m, 0);
for(int i=0; i<m; i++){
if(!group[ex[i]] || !group[ey[i]] || group[ex[i]] != group[ey[i]]) base[i] = 1;
else if(group[ex[i]] == 1){
if(abs(uDist[ex[i]] - uDist[ey[i]]) != 1) base[i] = 1;
}
else if(group[ex[i]] == 2){
if(abs(vDist[ex[i]] - vDist[ey[i]]) != 1) base[i] = 1;
}
}
for(int i=0; i<n; i++){
if(group[i] == 1) uVec.push_back(i);
if(group[i] == 2) vVec.push_back(i);
}
sort(uVec.begin(), uVec.end(), [&](int x, int y){
return uDist[x] < uDist[y];
});
sort(vVec.begin(), vVec.end(), [&](int x, int y){
return vDist[x] < vDist[y];
});
for(int i=0; i<(int)uVec.size(); i++) uIdx[uVec[i]] = i;
for(int i=0; i<(int)vVec.size(); i++) vIdx[vVec[i]] = i;
binarySearch(U, uVec, uIdx, 1);
binarySearch(V, vVec, vIdx, 2);
answer(U, V);
}
