#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 intime[maxn];
bool posetio[maxn];
vector<int> nisu;
vector<pair<int,int> > g2[maxn];
vector<int> redosled;
void bfs(int n,int m,int prva,int poc1,int poc2){
queue<int> bfs;
bfs.push(poc1);
bfs.push(poc2);
posetio[poc1]=true;
posetio[poc2]=true;
redosled.push_back(prva);
g2[poc1].push_back({poc2,prva});
g2[poc2].push_back({poc1,prva});
int t=0;
set<int> jesu;
jesu.emplace(prva);
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);
g2[node].push_back({u,ind});
g2[u].push_back({node,ind});
redosled.push_back(ind);
jesu.emplace(ind);
}
}
for(int i=0;i<m;i++) if(jesu.find(i)==jesu.end()) nisu.push_back(i);
}
bool bio[maxn];
set<int> tren;
vector<int> red;
void dfs(int node){
bio[node]=true;
for(auto [u,ind]:g2[node]){
if(bio[u]) continue;
tren.emplace(ind);
dfs(u);
}
}
int uradi(int n,int m,ll bez,int prva,int poc1,int poc2,vector<int> &u,vector<int> &v){
tren.clear();
for(int i=0;i<n;i++) bio[i]=false;
for(auto [u,ind]:g2[poc1]) if(u!=poc2) bio[u]=true;
dfs(poc1);
red.clear();
for(int i:redosled) if(tren.find(i)!=tren.end()) red.push_back(i);
int l=0;
int r=int(red.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:nisu) w[i]=1;
for(int i=mid;i<int(red.size());i++){
w[red[i]]=1;
}
if(ask(w)>bez){
ret=mid;
l=mid+1;
}else r=mid-1;
}
if(ret==0) return poc2;
if(intime[u[red[ret]]]>intime[v[red[ret]]]){
return u[red[ret]];
}else return v[red[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});
}
bfs(n,m,prva,u[prva],v[prva]);
int lik1=uradi(n,m,bez,prva,u[prva],v[prva],u,v);
int lik2=uradi(n,m,bez,prva,v[prva],u[prva],u,v);
//cout<<lik1<<" "<<lik2<<"\n";
answer(lik1,lik2);
}
