#include"highway.h"
#include<bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define ll long long
using namespace std;
int n,m,u[200005],v[200005],eg[200005],vt[200005],E;
vector<pair<int,int>>adj[200005];
void find_pair(int N,vector<int>U,vector<int>V,int A,int B){
n=N,m=U.size();
for(int i=0;i<m;i++)u[i]=U[i],v[i]=V[i],adj[u[i]].push_back({i,v[i]}),adj[v[i]].push_back({i,u[i]});
vector<int>w(m,0);
ll d0=ask(w);
int l=0,r=m-1,e;
while(l<r){
int mid=(l+r)>>1;
for(int i=0;i<=mid;i++)w[i]=1;
for(int i=mid+1;i<m;i++)w[i]=0;
ask(w)>d0?r=mid:l=mid+1;
}
e=l;
int vv[2]={u[e],v[e]},ans[2];
vector<int>dist[2];
for(int j=0;j<2;j++){
queue<int>q;
vector<int>d(n,-1);
d[vv[j]]=0,q.push(vv[j]);
for(int w;q.size();w=q.front(),q.pop())for(auto[i,nx]:adj[w])d[nx]==-1?(d[nx]=d[w]+1,q.push(nx),0):0;
dist[j]=d;
}
for(int j=0;j<2;j++){
queue<int>q;
vector<int>d(n,-1);
fill(eg,eg+m,-1),E=0,d[vv[j]]=0,q.push(vv[j]);
for(int w;q.size();w=q.front(),q.pop())for(auto[i,nx]:adj[w])dist[j][nx]<dist[j^1][nx]?(d[nx]==-1?(d[nx]=d[w]+1,vt[E]=nx,eg[i]=E++,q.push(nx),0):(d[nx]==d[w]+1?eg[i]=n:0)):i^e?eg[i]=n:0;
vector<int>c;
for(int i=0;i<E;i++)c.push_back(i);
while(c.size()>1){
int sz=c.size();
w.assign(m,0);
for(int i=0;i<sz/2;i++)w[eg[c[i]]]=1;
ll res=ask(w);
vector<int>nw;
res>d0?nw.insert(nw.end(),c.begin(),c.begin()+sz/2):nw.insert(nw.end(),c.begin()+sz/2,c.end()),c=nw;
}
ans[j]=c.empty()?vv[j]:vt[c[0]];
}
answer(ans[0],ans[1]);
}
