#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,dp[MAXN];
vector<pii> g[MAXN];
void bfs(int x){
fall(i,0,n-1) dp[i]=MAXN;
queue<int> fila; fila.push(x); dp[x]=0;
while(sz(fila)){
auto a=fila.front(); fila.pop();
for(auto [u,j]:g[a]) if(dp[u]==MAXN){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(V)-1){
g[V[i]].pb({U[i],i});
g[U[i]].pb({V[i],i});
}
vector<int> w(sz(V));
int dist=ask(w);
auto dnc=[&](auto &&self,vector<int> cand)->int{
if(sz(cand)==1) return cand[0];
for(auto&x:w)x=0;
vector<int> nc[2];
fall(i,0,sz(cand)/2-1) nc[0].pb(cand[i]);
fall(i,sz(cand)/2,sz(cand)-1) nc[1].pb(cand[i]);
for(auto x:nc[0])
for(auto [u,j]:g[x]) w[j]=1;
int dd=ask(w);
if(dd==dist) return self(self,nc[1]);
return self(self,nc[0]);
};
vector<int> al(n); iota(all(al),0);
int in_path=dnc(dnc,al);
bfs(in_path);
vector<int> cand(n); iota(all(cand),0);
sort(all(cand),[&](int a,int b){
return dp[a]>dp[b];
});
while(sz(cand)>1){
vector<int> nc[2];
for(auto&x:w)x=0;
fall(i,0,sz(cand)/2-1) nc[0].pb(cand[i]);
fall(i,sz(cand)/2,sz(cand)-1) nc[1].pb(cand[i]);
for(auto x:nc[0])
for(auto [u,j]:g[x]) w[j]=1;
int dd=ask(w);
if(dd==dist) cand=nc[1];
else cand=nc[0];
}
int ans=cand[0];
cand.resize(n); iota(all(cand),0);
bfs(ans);
sort(all(cand),[&](int a,int b){
return dp[a]>dp[b];
});
while(sz(cand)>1){
vector<int> nc[2];
for(auto&x:w)x=0;
fall(i,0,sz(cand)/2-1) nc[0].pb(cand[i]);
fall(i,sz(cand)/2,sz(cand)-1) nc[1].pb(cand[i]);
for(auto x:nc[0])
for(auto [u,j]:g[x]) w[j]=1;
int dd=ask(w);
if(dd==dist) cand=nc[1];
else cand=nc[0];
}
answer(ans,cand[0]);
}
