#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=9e4+10;
typedef pair<int,int> pii;
int n,dp[MAXN];
vector<pii> g[MAXN];
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[x])
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));
auto dist=ask(w);
vector<int> cand(n);
fall(i,0,n-1) cand[i]=i;
while(sz(cand)>1){
vector<int> ca[2];
fall(i,0,sz(cand)-1){
ca[i%2].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];
}
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;
});
while(sz(cand)>1){
vector<int> ca[2];
fall(i,0,sz(cand)-1){
ca[i%2].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(i!=ans1) 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)-1){
ca[i%2].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];
}
answer(cand[0],ans1);
}
