#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
int e[90001],d[90001],n,a,b;std::vector<int>u,v;std::vector<std::pair<int,int>>g[90001];
void find_pair(int n_, std::vector<int> u_, std::vector<int> v_, int A_, int B_) {
n=n_,u=u_,v=v_,a=A_,b=B_;
int m = u.size();
for(int i=0;i<m;++i)g[u[i]].push_back({v[i],i}),g[v[i]].push_back({u[i],i});
{
queue<pair<int,int>>q;
q.emplace(d[0]=0,0);
while(q.size()){auto[c,u]=q.front();q.pop();for(auto [v,i]:g[u])if(d[v]>c+1)q.emplace(d[v]=c+1,v),e[v]=i;}
}
vector<int>c(n);
iota(c.begin(),c.end(),0);
sort(c.begin(),c.end(),[](int i,int v){return d[i]<d[v];});
long long need;
{vector<int>qq(m,1); need=ask(qq);}
int z=0,l=0,r=n-1;
while(l<=r){
int m=(l+r)/2;
vector<int>qq(m);
for(int i=1;i<=m;++i)qq[e[i]]=1;
if (ask(qq)==need)z=m,r=m-1;
else l=m+1;
}
answer(0,z);
}
