#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 3;
ll n, a, b, m, dist;
vector<pair<int, int>> adj[N];
int get_last(int start){
queue<int> q;
q.push(start);
vector<bool> vis(n, false);
vis[start] = true;
vector<pair<int, int>> edges;
while(!q.empty()){
int u = q.front();
q.pop();
for(auto [to, idx]: adj[u]){
if(vis[to]) continue;
edges.push_back({to, idx});
q.push(to);
vis[to] = true;
}
}
int l = 0, r = n - 1;
while(l != r){
int mid = (l + r) >> 1;
vector<int> w(m, 1);
for(int i = 0; i <= mid; ++i)
w[edges[i].second] = 0;
if(ask(w) == dist)
r = mid;
else
l = mid + 1;
}
return edges[l].first;
}
void find_pair(int _n, std::vector<int> u, std::vector<int> v, int _a, int _b) {
m = u.size();
n = _n, a = _a, b = _b;
for(int i = 0; i < m; ++i){
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
dist = ask(vector<int>(m, 0));
int l = 0, r = m - 1;
while(l != r){
int mid = (l + r) >> 1;
vector<int> w(m, 1);
for(int i = 0; i <= mid; ++i)
w[i] = 0;
if(ask(w) == dist)
r = mid;
else
l = mid + 1;
}
int x = u[l];
int s = get_last(x);
int t = get_last(s);
answer(s, t);
}
