#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
#define maxn 90005
int n,m,a,b,dist[maxn][2],pedge[maxn][2],s[maxn];
ll d;
vector<ii> AL[maxn];
void find_pair(int _n,vi u,vi v,int _a,int _b){
n=_n;a=_a;b=_b;
m=u.size();
for(int i=0;i<m;++i){
AL[u[i]].pb({v[i],i});
AL[v[i]].pb({u[i],i});
}
vi w(m);
d=ask(w)/a;
vi pos;
for(int i=0;i<m;++i)pos.pb(i);
while(pos.size()!=1){
int x=pos.size();
vi w(m);
for(int i=0;i<x/2;++i)w[pos[i]]=1;
vi tmp;
if(ask(w)>d*a){
for(int i=0;i<x/2;++i)tmp.pb(pos[i]);
}
else{
for(int i=x/2;i<x;++i)tmp.pb(pos[i]);
}
swap(tmp,pos);
tmp.clear();
}
int f=pos[0];
vi r={u[f],v[f]};
//pf("rts: %d %d\n",r[0],r[1]);
memset(dist,-1,sizeof dist);
for(int i=0;i<2;++i){
queue<int> q;
dist[r[i]][i]=0;
q.push(r[i]);
while(!q.empty()){
int u=q.front();q.pop();
for(auto[v,x]:AL[u]){
if(dist[v][i]!=-1)continue;
dist[v][i]=dist[u][i]+1;
pedge[v][i]=x;
q.push(v);
}
}
}
/*
pf("d[0]: ");
for(int i=0;i<n;++i)pf("%d ",dist[i][0]);
pf("\n");
pf("d[1]: ");
for(int i=0;i<n;++i)pf("%d ",dist[i][1]);
pf("\n");
*/
//pf("s: ");
for(int i=0;i<n;++i){
if(dist[i][1]<dist[i][0])s[i]=1;
//pf("%d ",s[i]);
}
//pf("\n");
vi ans={0,0};
for(int x=0;x<2;++x){
vi pos;
for(int i=0;i<n;++i){
if(s[i]==x&&i!=r[x])pos.pb(pedge[i][x]);
}
//pf("pos %d: ",x);
//for(int i:pos)pf("%d ",i);
//pf("\n");
vi w(m,1);
for(int i:pos)w[i]=0;
//pf("w %d: ",x);
//for(int i=0;i<m;++i)pf("%d ",w[i]);
//pf("\n");
sort(all(pos),[&](int a,int b){return max(dist[u[a]][x],dist[v[a]][x])<max(dist[u[b]][x],dist[v[b]][x]);});
int lo=0,hi=pos.size()-1,mid,res=-1;
while(lo<=hi){
int mid=(lo+hi)>>1;
for(int i=0;i<=mid;++i)w[pos[i]]=1;
//pf("mid %d: %d\n",mid,ask(w));
if(ask(w)==d*b)res=mid,hi=mid-1;
else lo=mid+1;
for(int i=0;i<=mid;++i)w[pos[i]]=0;
}
if(res==0&&ask(w)==d*b)res=-1;
//pf("res %d: %d\n",x,res);
if(res==-1)ans[x]=r[x];
else{
int e=pos[res];
ans[x]=(dist[u[e]][x]>dist[v[e]][x])?u[e]:v[e];
}
}
//pf("%d %d\n",ans[0],ans[1]);
answer(ans[0],ans[1]);
}
