// moreflags=grader.cpp
// :(
#include "highway.h"
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<vector>
#include<cstdint>
#include<algorithm>
void find_pair(int number, std::vector<int> U, std::vector<int> V, int A, int B) {
std::vector<int> query(U.size(), 0);
auto const d1=ask(query); // a*(distance from S to T)
int i=0;
for(int step=1<<20; step>>=1;) if(i+step<(int)U.size()){
query.assign(i+step, 1); query.resize(U.size(), 0);
auto const d=ask(query);
if(d==d1) i+=step;
}
// now i is the maximum value such that there's a shortest path not passing through the first i edges
// therefore there must be a shortest path passing through edge [i]
struct Edge{int node, index;};
std::array<std::vector<Edge>, 2> edges; // edge indices in the bfs tree, split by sourceIndex,
// each one is ordered by distance from source node
// (node in each edge struct is the node farther from the corresponding source node)
std::array<int, 2> source{{U[i], V[i]}};
{
// construct adjacency list
std::vector<std::vector<Edge>> add(number);
for(int index=0; index<(int)U.size(); ++index){
auto const a=U[index], b=V[index];
add[a].push_back({b, index}); add[b].push_back({a, index});
}
// multisource bfs from edge [i]
struct Item{int node, sourceIndex;};
std::vector<Item> queue; queue.reserve(number);
std::vector<char> visited(number);
for(int i=0; i<2; ++i){
queue.push_back({source[i], i}); visited[source[i]]=true;
}
for(int start=0; start<(int)queue.size(); ++start){
auto const [node, sourceIndex]=queue[start];
for(auto [other, edgeIndex]: add[node]) if(not visited[other]){
edges[sourceIndex].push_back({other, edgeIndex});
visited[other]=true;
queue.push_back({other, sourceIndex});
}
}
}
std::array<int, 2> result;
for(int sourceIndex=0; sourceIndex<2; ++sourceIndex){
int j=(int)edges[sourceIndex].size();
for(int step=1<<20; step>>=1;) if(j-step>=0){
query.assign(U.size(), 1);
query[i]=0;
for(auto [other, index]: edges[not sourceIndex]) query[index]=0;
for(int k=0; k<j-step; ++k) query[edges[sourceIndex][k].index]=0;
if(ask(query)==d1) j-=step;
}
// now j is the smallest value such that the sourceIndex half of the shortest path
// is included in the first j nodes of edges[sourceIndex]
result[sourceIndex]=j==0 ? source[sourceIndex]: edges[sourceIndex][j-1].node;
}
answer(result[0], result[1]);
}
