#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
#define MAX_N 90004
//#include "grader.cpp"
int n ,m;
vector <pair <int ,int>> adj[MAX_N];
int par[MAX_N];
vector <pair<int ,int>> nodes;
void bfs(int s){
nodes.clear();
queue <pair<int,int>> nxt;
nxt.push({s ,par[s]});
while(!nxt.empty()){
int u = nxt.front().first ,f = nxt.front().second; nxt.pop();
// cout << u << endl;
nodes.push_back({u ,f});
for(auto e : adj[u])
nxt.push(e);
}
}
/**
4 4 1 3 1 3
0 1
0 2
0 3
1 2
*/
int solve(int u ,long long dist){
bfs(u);
int st = 0 ,en = nodes.size()-1 ,mid;
while(st < en){
mid = (st+en+1)>>1;
vector <int> w(m ,0);
for(int i=mid; i<=en; i++)
w[nodes[i].second] = 1;
if(ask(w) != dist)
st = mid;
else
en = mid-1;
}
return nodes[st].first;
}
vector <pair<int ,int>> t_adj[MAX_N];
void get_bfs_tree(int s){
vector <bool> vis(n); vis[s] = 1;
queue <int> nxt; nxt.push(s);
while(!nxt.empty()){
int u = nxt.front(); nxt.pop();
for(auto e : adj[u])
if(!vis[e.first]){
vis[e.first] = 1;
nxt.push(e.first);
t_adj[u].push_back(e);
par[e.first] = e.second;
}
}
for(int i=0; i<n; i++)
swap(adj[i] ,t_adj[i]);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N ,m = U.size();
for(int i=0; i<m; i++)
adj[U[i]].push_back({V[i] ,i}),
adj[V[i]].push_back({U[i] ,i});
long long dist = ask(vector<int>(m ,0));
int st = 0 ,en = m ,mid;
while(st < en){
mid = (st+en)>>1;
vector <int> w(m ,0);
for(int i=st; i<=mid; i++)
w[i] = 1;
if(ask(w) != dist)
en = mid;
else
st = mid+1;
}
get_bfs_tree(U[en]);
par[U[en]] = en;
adj[U[en]].erase(find(adj[U[en]].begin() ,adj[U[en]].end() ,make_pair(V[en] ,en)));
int s = solve(U[en] ,dist);
int t = solve(V[en] ,dist);
//cout << s << ' ' << t << endl;
answer(s ,t);
}
