#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn=90010;
vector<pair<int,int> > g[maxn];
int uradi(int n,int m,int a,int b,ll bez,int prva,int pocetak,int skoropocetak,vector<int> &u,vector<int> &v){
queue<int> bfs;
bfs.push(pocetak);
vector<bool> posetio(n,0);
posetio[pocetak]=true;
for(auto i:g[pocetak]){
if(i.first!=skoropocetak) posetio[i.first]=true;
}
vector<int> redosled;
vector<int> intime(n,0);
int t=0;
while(!bfs.empty()){
int node=bfs.front();
intime[node]=t++;
bfs.pop();
for(auto [u,ind]:g[node]){
if(posetio[u]) continue;
if(ind<prva) continue;
posetio[u]=true;
bfs.push(u);
redosled.push_back(ind);
}
}
int l=0;
int r=int(redosled.size())-1; // ?
int ret=-1;
while(l<=r){
int mid=l+(r-l)/2;
vector<int> w(m,0);
fill(w.begin(),w.begin()+prva,1);
for(int i=mid;i<int(redosled.size());i++){
w[redosled[i]]=1;
}
if(ask(w)>bez){
ret=mid;
l=mid+1;
}else r=mid-1;
}
if(intime[u[redosled[ret]]]>intime[v[redosled[ret]]]){
return u[redosled[ret]];
}else return v[redosled[ret]];
}
void find_pair(int n,vector<int> u,vector<int> v,int a,int b) {
int m=u.size();
int prva=0;
int l=1,r=m;
ll bez=ask(vector<int>(m,0));
while(l<=r){
int mid=l+(r-l)/2;
vector<int> w(m,0);
fill(w.begin(),w.begin()+mid,1);
if(ask(w)>bez){
prva=mid;
r=mid-1;
}else l=mid+1;
}
prva--;
for(int i=0;i<m;i++){
g[u[i]].push_back({v[i],i});
g[v[i]].push_back({u[i],i});
}
int lik1=uradi(n,m,a,b,bez,prva,u[prva],v[prva],u,v);
int lik2=uradi(n,m,a,b,bez,prva,v[prva],u[prva],u,v);
//cout<<lik1<<" "<<lik2<<"\n";
answer(lik1,lik2);
}
