#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int n, m, k, TT=0;
vector<int> booga;
vector<vector<pii> > adj;
vector<vector<int> > dj;
int calc(vector<pii> ord){
int low=-1, high=ord.size();
while (low+1<high){
int mid=(low+high)/2;
vector<signed> temp(m, 0);
for (int i=0; i<m; ++i)if (booga[i])temp[i]=1;
for (int i=mid; i<ord.size(); ++i)temp[ord[i].se]=1;
int ress=ask(temp);
if (k==ress)high=mid;
else low=mid;
}
if (low==-1)return -1;
return ord[low].fi;
}
bool custom(pii a, pii b){
return dj[TT][a.fi]<dj[TT][b.fi];
}
void find_pair(signed N, vector<signed> u, vector<signed> v, signed a, signed b){
n=N, m=u.size();
adj.clear();
dj.clear();
booga.clear();
booga.resize(m, 1);
adj.resize(n);
vector<pii> ord;
vector<signed> temp(m, 0);
k=ask(temp);
for (int i=0; i<m; ++i){
adj[u[i]].pb(mp(v[i], i));
adj[v[i]].pb(mp(u[i], i));
}
int low=0, high=m;
while (low+1<high){
int mid=(low+high)/2;
vector<signed> temp(m, 0);
for (int i=0; i<mid; ++i)temp[i]=1;
if (ask(temp)==k)low=mid;
else high=mid;
}
vector<vector<int> > par(2, vector<int>(n, -1));
dj.resize(2, vector<int>(n, -1));
queue<pii> q;
dj[0][u[low]]=dj[1][v[low]]=0;
booga[low]=0;
q.push(mp(0, u[low]));
q.push(mp(1, v[low]));
while (q.size()){
int node=q.front().se, p=q.front().fi;
q.pop();
for (auto num:adj[node])if (dj[p][num.fi]==-1)dj[p][num.fi]=dj[p][node]+1, q.push(mp(p, num.fi)), par[p][num.fi]=num.se;
}
vector<int> ans, ooga;
ooga.pb(u[low]);
ooga.pb(v[low]);
for (int i=0; i<n; ++i){
if (dj[0][i]<dj[1][i]&&par[0][i]!=-1)booga[par[0][i]]=0;
if (dj[1][i]<dj[0][i]&&par[1][i]!=-1)booga[par[1][i]]=0;
}
for (int i=0; i<2; ++i){
vector<pii> ord;
for (int j=0; j<n; ++j)if (dj[i][j]<dj[!i][j]&&par[i][j]!=-1)ord.pb(mp(j, par[i][j]));
TT=i;
sort(ord.begin(), ord.end(), custom);
int res=calc(ord);
if (res==-1)ans.pb(ooga[i]);
else ans.pb(res);
}
answer(ans[0], ans[1]);
}
