#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
ii vis[90005];
vector<ii> adj[90005];
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
int m = U.size();
vector<int> w; w.assign(m, 1);
for(int i = 0;i < m;i++){
adj[U[i]].push_back(ii(V[i],i));
adj[V[i]].push_back(ii(U[i],i));
}
long long allHeavy = ask(w);
int low = 0, high = m - 1;
while(low < high){
int s = (high + low) / 2;
for(int i = 0;i < m;i++) w[i] = !(low <= i && i <= s);
if(ask(w) == allHeavy) low = s + 1;
else high = s;
}
int sRoot = U[low], tRoot = V[low];
vis[sRoot] = ii(1,0); vis[tRoot] = ii(2,0);
queue<int> bfs; bfs.push(sRoot); bfs.push(tRoot);
vector<int> sEdges, tEdges;
while(!bfs.empty()){
int u = bfs.front(); bfs.pop();
for(ii v : adj[u]){
if(vis[v.first] == ii(0,0)){
bfs.push(v.first);
vis[v.first] = ii(vis[u].first, vis[u].second + 1);
if(vis[u].first == 1) sEdges.push_back(v.second);
else tEdges.push_back(v.second);
}
}
}
int S, T;
w.assign(m, 1);
low = -1, high = sEdges.size() - 1;
while(low < high){
int s = (high + low) / 2;
for(int i = 0;i < (int) sEdges.size();i++) w[sEdges[i]] = !(low <= i && i <= s);
if(ask(w) == allHeavy) low = s + 1;
else high = s;
}
if(low == -1) S = sRoot;
else{
int u = U[sEdges[low]], v = V[sEdges[low]];
if(vis[u].second > vis[v].second) S = u;
else S = v;
}
w.assign(m, 1);
low = -1, high = tEdges.size() - 1;
while(low < high){
int s = (high + low) / 2;
for(int i = 0;i < (int) tEdges.size();i++) w[tEdges[i]] = !(low <= i && i <= s);
if(ask(w) == allHeavy) low = s + 1;
else high = s;
}
if(low == -1) T = tRoot;
else{
int u = U[tEdges[low]], v = V[tEdges[low]];
if(vis[u].second > vis[v].second) T = u;
else T = v;
}
answer(S, T);
}
