#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
int n;
int m;
const int N = 130500;
int dis[2][N];
int par[2][N];
int c;
vector<pii> T[N];
void bfs(int u){
dis[c][u]=0;
par[c][u]=-1;
queue<int> bf;
bf.push(u);
int node;
while(!bf.empty()){
node = bf.front();
bf.pop();
for(auto x : T[node]){
if(dis[c][x.fi] > dis[c][node] + 1){
dis[c][x.fi] = dis[c][node] + 1;
par[c][x.fi] = x.se;
bf.push(x.fi);
}
}
}
c ++ ;
}
struct Node{
int dist;
int parid;
int ndx;
bool operator<(const Node &F) const {
return dist < F.dist;
}
};
void find_pair(int _n, vector<int> u, vector<int> v, int a, int b) {
n = _n;
m = u.size();
vector<int> w(m);
for(int i = 0 ; i < m ; i ++ ){
w[i] = 0;
T[u[i]].push_back(mp(v[i], i));
T[v[i]].push_back(mp(u[i], i));
}
ll dist = ask(w);
int li = 0, ri = m-1;
int mid;
while(li < ri){
mid = (li + ri) / 2;
for(int j = 0 ; j < m ; j ++ ){
if(j <= mid)
w[j] = 0;
else
w[j] = 1;
}
if(ask(w) == dist)
ri = mid;
else
li = mid + 1;
}
int p = u[li];
int q = v[li];
int man = li;
for(int i = 0 ; i < 2; i ++ ){
for(int j = 0 ; j < n; j ++ ){
dis[i][j] = (int)1e9;
par[i][j] = -1;
}
}
bfs(p);
bfs(q);
vector<Node> cell[2];
for(int i = 0 ; i < n; i ++ ){
if(dis[0][i] == dis[1][i]){
continue;
}
else if(dis[0][i] < dis[1][i]){
cell[0].push_back({dis[0][i], par[0][i], i});
}
else{
cell[1].push_back({dis[1][i], par[1][i], i});
}
}
sort(cell[0].begin(), cell[0].end());
sort(cell[1].begin(), cell[1].end());
li = 0, ri = (int)cell[0].size() - 1;
while(li < ri){
mid = (li + ri) / 2;
for(int i = 0 ; i < m ; i ++ ){
w[i] = 1;
}
w[man] = 0;
for(auto f : cell[1]){
if(f.parid != -1){
w[f.parid] = 0;
}
}
for(int i = 0 ; i <= mid; i ++ ){
if(cell[0][i].parid != -1)
w[cell[0][i].parid] = 0;
}
if(ask(w) == dist)
ri = mid;
else
li = mid + 1;
}
int S,T;
S = cell[0][li].ndx;
li = 0, ri = (int)cell[1].size() - 1;
while(li < ri){
mid = (li + ri) / 2;
for(int i = 0 ; i < m; i ++ ){
w[i] = 1;
}
w[man] = 0;
for(auto f : cell[0]){
if(f.parid != -1){
w[f.parid] = 0;
}
}
for(int i = 0 ; i <= mid; i ++ ){
if(cell[1][i].parid != -1){
w[cell[1][i].parid] = 0;
}
}
if(ask(w) == dist)
ri = mid;
else
li = mid + 1;
}
T = cell[1][li].ndx;
answer(S,T);
}
