#include "highway.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int n, m;
ll A, B;
vector<vector<pair<int, int>>> graph;
ll def;
int find_node(int root){
vector<int> dis(n, -1);
queue<int> Q;
dis[root] = 0;
Q.push(root);
vector<int> p(n, -1);
while(!Q.empty()){
int nd = Q.front(); Q.pop();
for(auto [x, i]: graph[nd]) if(dis[x] == -1){
dis[x] = dis[nd]+1;
p[x] = i;
Q.push(x);
}
}
vector<int> o(n);
for(int i = 0; i < n; i++) o[i] = i;
sort(o.begin(), o.end(), [&](int a, int b){
return dis[a] > dis[b];
});
ll def = ask(vector<int>(m, 0));
int a = 0, b = n-1;
while(a < b){
int md = (a+b)/2;
vector<int> w(m, 0);
for(int i = 0; i <= md; i++) if(p[o[i]] != -1) w[p[o[i]]] = 1;
ll x = ask(w);
if(x > def) b = md;
else a = md+1;
}
return o[a];
}
void find_pair(int _n, vector<int> U, vector<int> V, int _A, int _B){
swap(n, _n);
m = U.size();
A = _A, B = _B;
graph.resize(n);
for(int i = 0; i < m; i++){
graph[U[i]].pb({V[i], i});
graph[V[i]].pb({U[i], i});
}
def = ask(vector<int>(m, 0));
int a = 0, b = m-1;
while(a < b){
int md = (a+b)/2;
vector<int> w(m, 0);
for(int i = 0; i <= md; i++) w[i] = 1;
ll x = ask(w);
if(x > def) b = md;
else a = md+1;
}
int nd = U[a];
int s = find_node(nd);
int t = find_node(s);
answer(s, t);
}
