#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define sz(x) (int) x.size()
#define pb push_back
#define all(x) x.begin(),x.end()
const int MAXN=2e5+10;
typedef pair<int,int> pii;
int n;
ll dp[MAXN];
vector<pii> g[MAXN];
void dfs(int x){
for(auto [u,lala]:g[x]){
if(dp[u]==-1){
dp[u]=dp[x]+1;
dfs(u);
}
}
}
void call(int x){
fall(i,0,n-1) dp[i]=-1;
dp[x]=0;
dfs(x);
}
void bfs(int x){
fall(i,0,n-1) dp[i]=n+1;
queue<int> fila; fila.push(x); dp[x]=0;
while(!fila.empty()){
auto a=fila.front(); fila.pop();
for(auto[u,j]:g[a])
if(dp[u]==n+1){
dp[u]=dp[a]+1;
fila.push(u);
}
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n=N;
fall(i,0,sz(U)-1){
g[U[i]].pb({V[i],i});
g[V[i]].pb({U[i],i});
}
vector<int> w(sz(U));
ll dist=ask(w);
call(0);
vector<int> cand(n); iota(all(cand),0);
sort(all(cand),[&](int a,int b){
if(dp[a]!=dp[b]) return dp[a]>dp[b];
return a>b;
});
while(sz(cand)>1){
vector<int> ca[2];
fall(i,0,sz(cand)/2-1){
ca[0].pb(cand[i]);
}
fall(i,sz(cand)/2,sz(cand)-1) ca[1].pb(cand[i]);
for(auto&u:w) u=0;
for(auto x:ca[0]){
for(auto [u,j]:g[x]) w[j]=1;
}
if(ask(w)!=dist) cand=ca[0];
else cand=ca[1];
//cout<<ask(w)<<" ";
for(auto&u:w) u=0;
for(auto x:ca[1]){
for(auto [u,j]:g[x]) w[j]=1;
}
//cout<<ask(w)<<"\n";
}
auto ver=cand[0];
bfs(ver);
cand.clear();
fall(i,0,n-1) if(i!=ver) cand.pb(i);
sort(all(cand),[&](int a,int b){
if(dp[a]!=dp[b]) return dp[a]>dp[b];
return a>b;
});
/*cout<<dist/A<<"\n";
for(auto x:cand) if(x==88821 || x==8389 || x==30652) cout<<x<<" "<<dp[x]<<"\n";
cout<<"\n";*/
while(sz(cand)>1){
vector<int> ca[2];
fall(i,0,sz(cand)/2-1){
ca[0].pb(cand[i]);
}
fall(i,sz(cand)/2,sz(cand)-1) ca[1].pb(cand[i]);
for(auto&u:w)u=0;
for(auto x:ca[0]){
for(auto[u,j]:g[x]) w[j]=1;
}
if(ask(w)!=dist) cand=ca[0];
else cand=ca[1];
}
int ans1=cand[0];
bfs(ans1);
cand.clear();
fall(i,0,n-1) if(dp[i]==(dist/A)) cand.pb(i);
sort(all(cand),[&](int a,int b){
if(dp[a]!=dp[b]) return dp[a]>dp[b];
return a>b;
});
while(sz(cand)>1){
vector<int> ca[2];
fall(i,0,sz(cand)/2-1){
ca[0].pb(cand[i]);
}
fall(i,sz(cand)/2,sz(cand)-1) ca[1].pb(cand[i]);
for(auto&u:w)u=0;
for(auto x:ca[0]){
for(auto[u,j]:g[x]) w[j]=1;
}
if(ask(w)!=dist) cand=ca[0];
else cand=ca[1];
}
//cout<<ans1<<"\n";
answer(cand[0],ans1);
}
