#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
using ll = long long;
vector<pair<int,int>> g[101010];
vector<pair<int,int>> t[2][101010];
void find_pair(int n, std::vector<int> p, std::vector<int> q, int a, int b) {
int m=p.size();
for(int i=0;i<m;i++){
g[p[i]].push_back({q[i],i});
g[q[i]].push_back({p[i],i});
}
int ok=0,ng=m;
vector<int> w(m,0);
ll l=ask(w);
while(abs(ok-ng)>1){
int mid=(ok+ng)/2;
vector<int> w2(m);
for(int i=0;i<mid;i++) w2[i]=1;
if(ask(w2)==l) ok=mid;
else ng=mid;
}
int u=p[ok],v=q[ok],uv=ok;
queue<int> qu;
qu.push(u);
qu.push(v);
vector<int> seen(n,0);
vector<int> d(n,0);
vector<int> id(n,-1);
//u,v それぞれ最短路
seen[u]=1;
seen[v]=2;
while(qu.size()){
int nv=qu.front();
qu.pop();
for(auto e:g[nv]){
if(seen[e.fi]==0){
seen[e.fi]=seen[nv];
d[e.fi]=d[nv]+1;
qu.push(e.fi);
id[e.fi]=e.se;
t[seen[e.fi]][e.fi].pb({nv,e.se});
}
}
}
int s=-1,t=-1;
for(int ty=1;ty<=2;ty++){
vector<pair<int,int>> vs;
for(int i=0;i<n;i++){
if(seen[i]==ty) vs.pb({d[i],i});
}
sort(vs.begin(),vs.end());
while(vs.size()>1){
int m2=vs.size();
int mid=m2/2;
vector<int> as(m,1);
as[uv]=0;
for(int i=0;i<n;i++) if(id[i]>=0) as[id[i]]=0;
for(int i=mid;i<m2;i++) as[id[vs[i].se]]=1;
ll l2=ask(as);
if(l2==l){
for(int i=mid;i<m2;i++) vs.pop_back();
}
else{
reverse(vs.begin(),vs.end());
for(int i=0;i<mid;i++) vs.pop_back();
reverse(vs.begin(),vs.end());
}
}
if(ty==1) s=vs[0].se;
else t=vs[0].se;
}
answer(s,t);
}
