#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
map<pair<ll, ll>, ll> mp;
vector<ll> adj[90005];
ll dist[2][90005], t;
bool cmp(ll x, ll y)
{
return dist[t][x]<dist[t][y];
}
void find_pair(int n, vector<int> uu, vector<int> vv, int a, int b)
{
ll m=uu.size();
for (ll i=0; i<m; i++)
{
adj[uu[i]].push_back(vv[i]);
adj[vv[i]].push_back(uu[i]);
mp[{uu[i], vv[i]}]=mp[{vv[i], uu[i]}]=i;
}
vector<int> tmp(m, 0);
ll res=ask(tmp), l=0, r=m-1;
while (l<r)
{
ll mid=(l+r)/2;
for (ll i=0; i<=mid; i++)
tmp[i]=1;
for (ll i=mid+1; i<m; i++)
tmp[i]=0;
if (ask(tmp)==res)
l=mid+1;
else
r=mid;
}
ll node[2]={uu[l], vv[l]};
for (ll i=0; i<2; i++)
{
queue<ll> q;
for (ll j=0; j<n; j++)
dist[i][j]=1e9;
dist[i][node[i]]=0;
q.push(node[i]);
while (!q.empty())
{
ll u=q.front();
q.pop();
for (ll v:adj[u])
{
if (dist[i][u]+1<dist[i][v])
{
dist[i][v]=dist[i][u]+1;
q.push(v);
}
}
}
}
ll ans[2];
for (t=0; t<2; t++)
{
vector<ll> vec;
for (ll i=0; i<n; i++)
if (dist[t][i]<dist[t^1][i])
vec.push_back(i);
sort(vec.begin(), vec.end(), cmp);
ll L=0, R=vec.size()-1;
while (L<R)
{
ll mid=(L+R+1)/2;
vector<int> tmp2(m, 0);
for (ll i=0; i<m; i++)
{
if (i==l)
continue;
ll type1=(dist[t][uu[i]]<dist[t^1][uu[i]]?1:(dist[t][uu[i]]>dist[t^1][uu[i]]?3:2));
ll type2=(dist[t][vv[i]]<dist[t^1][vv[i]]?1:(dist[t][vv[i]]>dist[t^1][vv[i]]?3:2));
if (type1==2 || type2==2 || type1!=type2)
tmp2[i]=1;
}
for (ll i=mid; i<vec.size(); i++)
for (ll j:adj[i])
if (dist[t][j]<dist[t][i])
tmp2[mp[{i, j}]]=1;
if (ask(tmp2)==res)
R=mid-1;
else
L=mid;
}
ans[t]=vec[L];
}
answer(ans[0], ans[1]);
}
