#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define MAXN 90001
int n,m,a,b;
vector<pair<int,int>> adj[MAXN];
int dist[2][MAXN];pair<int,int> parent[2][MAXN];
vector<int> state;queue<int> bfsq;
vector<int> nodes[2][MAXN];
void bfs(int p,int root)
{
for (int node=0;node<n;node++) {dist[p][node]=INT_MAX;parent[p][node]={-1,-1};}
dist[p][root]=0;bfsq.push(root);
while (!bfsq.empty())
{
int node=bfsq.front();bfsq.pop();
for (pair<int,int> edge:adj[node])
{
if (dist[p][edge.first]!=INT_MAX) continue;
dist[p][edge.first]=dist[p][node]+1;
parent[p][edge.first]={node,edge.second};
bfsq.push(edge.first);
}
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
/// za debugovanje
n=N;m=(int)U.size();a=A;b=B;
for (int edge=0;edge<m;edge++) {adj[U[edge]].push_back({V[edge],edge});adj[V[edge]].push_back({U[edge],edge});}
for (int i=0;i<m;i++) state.push_back(0);
long long initial=ask(state);
int l=0,r=m-1,rez=-1;
while (l<=r)
{
int mid=(l+r)/2;
for (int pos=0;pos<=mid;pos++) state[pos]=1;
long long curr=ask(state);
if (curr==initial) l=mid+1;
else {rez=mid;r=mid-1;}
for (int pos=0;pos<=mid;pos++) state[pos]=0;
}
int index=rez;//cout<<rez<<endl;
int root1=U[index],root2=V[index];
bfs(0,root1),bfs(1,root2);//cout<<root1<<" "<<root2<<endl;
for (int i=0;i<m;i++) state[i]=1;
for (int node=0;node<n;node++)
{
if (dist[0][node]==dist[1][node]) continue;
if (dist[0][node]<dist[1][node])
{
nodes[0][dist[0][node]].push_back(node);
if (parent[0][node].first!=-1) state[parent[0][node].second]=0;
}
if (dist[1][node]<dist[0][node])
{
nodes[1][dist[1][node]].push_back(node);
if (parent[1][node].first!=-1) state[parent[1][node].second]=0;
}
}
state[index]=0;//cout<<state<<endl;
l=1,r=n,rez=0;
while (l<=r)
{
int mid=(l+r)/2;
for (int depth=mid;depth<=n;depth++)
{
for (int node:nodes[0][depth]) state[parent[0][node].second]=1;
}
long long curr=ask(state);
if (curr!=initial) {rez=mid;l=mid+1;}
else r=mid-1;
for (int depth=mid;depth<=n;depth++)
{
for (int node:nodes[0][depth]) state[parent[0][node].second]=0;
}
}
int depth0=rez;//cout<<depth0<<endl;
l=1,r=n,rez=0;
while (l<=r)
{
int mid=(l+r)/2;
for (int depth=mid;depth<=n;depth++)
{
for (int node:nodes[1][depth]) state[parent[1][node].second]=1;
}
long long curr=ask(state);
if (curr!=initial) {rez=mid;l=mid+1;}
else r=mid-1;
for (int depth=mid;depth<=n;depth++)
{
for (int node:nodes[1][depth]) state[parent[1][node].second]=0;
}
}
int depth1=rez;//cout<<depth1<<endl;
int node0=-1,node1=-1;
if (depth0==0) node0=nodes[0][0][0];
else
{
l=0,r=(int)nodes[0][depth0].size()-1,rez=-1;
while (l<=r)
{
int mid=(l+r)/2;
for (int pos=0;pos<=mid;pos++) state[parent[0][nodes[0][depth0][pos]].second]=1;
long long curr=ask(state);
if (curr!=initial) {rez=mid;r=mid-1;}
else l=mid+1;
for (int pos=0;pos<=mid;pos++) state[parent[0][nodes[0][depth0][pos]].second]=0;
}
node0=nodes[0][depth0][rez];
}
if (depth1==0) node1=nodes[1][0][0];
else
{
l=0,r=(int)nodes[1][depth1].size()-1,rez=-1;
while (l<=r)
{
int mid=(l+r)/2;
for (int pos=0;pos<=mid;pos++) state[parent[1][nodes[1][depth1][pos]].second]=1;
long long curr=ask(state);
if (curr!=initial) {rez=mid;r=mid-1;}
else l=mid+1;
for (int pos=0;pos<=mid;pos++) state[parent[1][nodes[1][depth1][pos]].second]=0;
}
node1=nodes[1][depth1][rez];
}
answer(node0,node1);return;
}
