#include "highway.h"
#include <bits/stdc++.h>
#define MAX 1000000000000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vi;
vector<vi> G;
vector<int> hl;
ll conc[110];
int isq[110];
ll m,a,b,n;
ll dis[110];
void dijkstra(int x){
memset(isq,0,sizeof isq);
for(int i=0;i<n;i++) dis[i]=MAX;
dis[x]=0;
priority_queue<ii,vector<ii>,greater<ii>>pq;
pq.push(ii(0,x));
while(!pq.empty()){
int u=pq.top().second;
isq[u]=0;
pq.pop();
for(auto &v:G[u]){
ll cos;
if(hl[v.second]==1) cos=b;
else cos=a;
if(dis[v.first]>dis[u]+cos){
dis[v.first]=dis[u]+cos;
if(!isq[v.first]){
pq.push(ii(dis[v.first],v.first));
isq[v.first]=1;
}
}
}
}
}
vector<int> path;
int vis[90010];
void dfs(int u){
path.push_back(u);
vis[u]=1;
for(auto &v:G[u]){
if(!vis[v.first]) dfs(v.first);
}
}
void line_graph(int u){
memset(vis,0,sizeof vis);
dfs(u);
hl.assign(m,0);
int w=ask(hl);
int no=w/a;
int l=-1,r=m;
ll aux;
while(r-l>1){
int mid=(l+r)/2;
for(int i=0;i<mid;i++) hl[i]=1;
for(int i=mid;i<m;i++) hl[i]=0;
aux=ask(hl);
// cout<<l<<" "<<r<<" "<<mid<<" "<<aux<<endl;
if(aux==w) l=mid;
else r=mid;
/*for(int i=0;i<m;i++) cout<<hl[i]<<" ";
cout<<endl;*/
}
/* for(int i=0;i<path.size();i++){
cout<<path[i]<<" ";
}
cout<<endl;
cout<<l<<endl;
cout<<w<<endl<<no<<endl;*/
dijkstra(path[l]);
aux=ask(hl);
if(dis[path[l+no]]==aux){
answer(path[l],path[l+no]);
}
else {
reverse(path.begin(),path.end());
if(l+no>=n) answer(path[l],path[l-no]);
else
answer(path[l],path[l+no]);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n=N;
a=A;
b=B;
G.resize(N+1);
for(int i=0;i<U.size();i++){
int u=U[i],v=V[i];
G[u].push_back(ii(v,i));
G[v].push_back(ii(u,i));
}
bool sw=0;
int id=-1;
for(int i=0;i<N;i++){
if(G[i].size()>2) sw=1;
if(G[i].size()==1 and id==-1) id=i;
}
m=U.size();
if(sw==1){
memset(conc,0,sizeof conc);
hl.assign(m,0);
for(int i=0;i<m;i++){
hl[i]=1;
dijkstra(0);
ll co=ask(hl);
for(int j=0;j<N;j++){
if(dis[j]==co){
conc[j]++;
}
}
hl[i]=0;
}
ll t,ma=-1;
for(int i=0;i<N;i++){
if(conc[i]>ma){
ma=conc[i];
t=i;
}
}
answer(0,t);
}
else{
line_graph(id);
}
}
