#include "highway.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cassert>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
int n, m;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B){
n = N;
m = (int)U.size();
vector<vector<pair<int, int>>> graph(n);
for(int i = 0; i < m; i++){
graph[U[i]].emplace_back(V[i], i);
graph[V[i]].emplace_back(U[i], i);
}
vector<int> que(m);
ll len = ask(que);
auto reset = [&](){
for(int i = 0; i < m; i++) que[i] = 0;
};
int l = 0, r = m - 1;
while(l < r){
int mid = (l + r) >> 1;
reset();
for(int i = 0; i <= mid; i++) que[i] = 1;
if(ask(que) != len) r = mid;
else l = mid + 1;
}
int u = U[l], v = V[l];
vector<int> disu(n, -1), disv(n, -1);
vector<int> edu(n), edv(n);
vector<bool> visu(m), visv(m);
disu[u] = 0;
disv[v] = 0;
queue<int> q;
q.push(u);
while(!q.empty()){
int node = q.front();
q.pop();
for(auto &[x, eid]: graph[node]){
if(disu[x] == -1){
visu[eid] = 1;
edu[x] = eid;
disu[x] = disu[node] + 1;
q.push(x);
}
}
}
q.push(v);
while(!q.empty()){
int node = q.front();
q.pop();
for(auto &[x, eid]: graph[node]){
if(disv[x] == -1){
visv[eid] = 1;
edv[x] = eid;
disv[x] = disv[node] + 1;
q.push(x);
}
}
}
vector<pair<pair<int, int>, int>> bsu, bsv;
for(int i = 0; i < n; i++){
if(i == u || i == v) continue;
if(disu[i] < disv[i]) bsu.push_back(make_pair(make_pair(disu[i], edu[i]), i)), visv[i] = 0;
else if(disv[i] < disu[i]) bsv.push_back(make_pair(make_pair(disv[i], edv[i]), i)), visu[i] = 0;
else visu[i] = 0, visv[i] = 0;
//cout << i << " " << disu[i] << " " << disv[i] << "\n";
}
sort(bsu.begin(), bsu.end());
sort(bsv.begin(), bsv.end());
auto reset2 = [&](bool flag){
for(int i = 0; i < m; i++){
if(((!flag) && visu[i]) || (flag && visv[i])) que[i] = 0;
else que[i] = 1;
}
};
l = 0, r = (int)bsu.size();
int sz = r;
while(l < r){
int mid = ((l + r) >> 1);
reset2(0);
for(int i = mid; i < sz; i++) que[bsu[i].first.second] = 1;
if(ask(que) == len) r = mid;
else l = mid + 1;
}
int s, t;
if(l == 0) s = u;
else s = bsu[l - 1].second;
l = 0, r = (int)bsv.size();
sz = r;
while(l < r){
int mid = (l + r) >> 1;
reset2(1);
for(int i = mid; i < sz; i++) que[bsv[i].first.second] = 1;
if(ask(que) == len) r = mid;
else l = mid + 1;
}
if(l == 0) t = v;
else t = bsv[l - 1].second;
//cout << u << " " << v << " " << s << " " << t << "\n";
//for(int i = 0; i < (int)bsu.size(); i++) cout << bsu[i].first.first << " " << bsu[i].first.second << " " << bsu[i].second << "\n";
//for(int i = 0; i < (int)bsv.size(); i++) cout << bsv[i].first.first << " " << bsv[i].first.second << " " << bsv[i].second << "\n";
answer(s, t);
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp highway.cpp
