#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> VI;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define RREP(i,j,k) for(register int i=(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define MST(a,v) memset(a,(v),sizeof a)
#define pb push_back
#define mid (l+r>>1)
const int maxn=9e4+9,inf=1<<30;
int n,m,d1[maxn],d2[maxn],p1[maxn],p2[maxn];
long long o;
vector<pii>G[maxn];
VI g1[maxn],g2[maxn],w;
queue<int>Q;
void bfs(int s,int*dis,int*par){
fill(dis,dis+n,inf);
dis[s]=0;
Q.push(s);
while(!Q.empty()){
int u=Q.front();Q.pop();
REP(i,0,G[u].size()){
int v=G[u][i].first;
if(dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
par[v]=G[u][i].second;
Q.push(v);
}
}
}
}
int find(VI&vt,int*par){
int l=0,r=vt.size();
while(l+1<r){
REP(i,1,mid)w[par[vt[i]]]=0;
REP(i,mid,vt.size())w[par[vt[i]]]=1;
if(ask(w)>o)l=mid;
else r=mid;
}
return vt[l];
}
void find_pair(int _n,VI uu,VI vv,int a,int b){
n=_n;
m=uu.size();
w.resize(m);
REP(i,0,m)w[i]=0;
o=ask(w);
int l=0,r=m;
while(l+1<r){
REP(i,0,mid)w[i]=0;
REP(i,mid,m)w[i]=1;
if(ask(w)>o)l=mid;
else r=mid;
}
int ee=l;
REP(i,0,m){
int u=uu[i],v=vv[i];
G[u].pb(pii(v,i)),G[v].pb(pii(u,i));
}
bfs(uu[ee],d1,p1);
bfs(vv[ee],d2,p2);
VI v1,v2;
REP(i,0,n){
if(d1[i]<d2[i])v1.pb(i);
else v2.pb(i);
}
sort(ALL(v1),[](int x,int y){return d1[x]<d1[y];});
sort(ALL(v2),[](int x,int y){return d2[x]<d2[y];});
REP(i,0,m)w[i]=1;
w[ee]=0;
REP(i,1,v1.size())w[p1[v1[i]]]=0;
REP(i,1,v2.size())w[p2[v2[i]]]=0;
int u=find(v1,p1);
REP(i,0,m)w[i]=1;
w[ee]=0;
REP(i,1,v1.size())w[p1[v1[i]]]=0;
REP(i,1,v2.size())w[p2[v2[i]]]=0;
int v=find(v2,p2);
answer(u,v);
}
