#include "highway.h"
using namespace std;
tuple<vector<int>, vector<vector<int > > > distances(int N, vector<int> neighbors[], vector<int> out_edges[], int u){
vector<int> distances(N);
vector<vector<int> > path_edges(N);
distances[u] = 0;
int to_reach = N - 1;
bool reached_past[N];
bool reached_current[N];
for(int i = 0; i < N; i++){
reached_past[i] = false;
reached_current[i] = false;
}
reached_past[u] = true;
vector<int> current_generation = {u};
vector<int> next_generation;
int gen = 0;
while(to_reach != 0){
next_generation = {};
for(auto vertex = current_generation.begin(); vertex != current_generation.end(); vertex++){
for(int i = 0; i < neighbors[*vertex].size(); i++){
int neighbor = neighbors[*vertex][i];
int edge = out_edges[*vertex][i];
if(!reached_past[neighbor]){
path_edges[neighbor].push_back(edge);
if(!reached_current[neighbor]){
reached_current[neighbor] = true;
next_generation.push_back(neighbor);
}
}
}
}
gen++;
for(auto vertex = next_generation.begin(); vertex != next_generation.end(); vertex++){
reached_past[*vertex] = true;
distances[*vertex] = gen;
}
to_reach -= next_generation.size();
current_generation = next_generation;
}
return make_tuple(distances, path_edges);
}
int search_endpoint(int N, int M, int u, vector<int> w, vector<int> distances, vector<vector<int> > path_edges, vector<int> opposing_distances, long long distance){
vector<int> distance_classes[N];
for(int i = 0; i < N; i++){
distance_classes[distances[i]].push_back(i);
}
vector<int> candidates;
for(int i = 0; i < N; i++){
for(auto it = distance_classes[i].begin(); it != distance_classes[i].end(); it++){
if(opposing_distances[*it] - distances[*it] == 1){
candidates.push_back(*it);
}
}
}
vector<int> w_search = w;
int start = 0;
int end = candidates.size();
bool covered = false;
while(end != start + 1){
int median = (start + end) / 2;
if(covered){
for(int i = start; i < median; i++){
int vertex = candidates[i];
for(auto it = path_edges[vertex].begin(); it != path_edges[vertex].end(); it++){
w_search[*it] = w[*it];
}
}
}else{
for(int i = median; i < end; i++){
int vertex = candidates[i];
for(auto it = path_edges[vertex].begin(); it != path_edges[vertex].end(); it++){
w_search[*it] = true;
}
}
}
bool found = ask(w_search) != distance;
if(found){
start = median;
}else{
end = median;
}
covered = found;
}
return candidates[start];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
vector<int> w(M);
for(int i = 0; i < M; i++){
w[i] = false;
}
long long distance = ask(w);
int start = 0;
int end = M;
while(end != start + 1){
int median = (start + end) / 2;
for(int i = start; i < median; i++){
w[i] ^= true;
}
if((ask(w) == distance) ^ w[start]){
end = median;
}else{
start = median;
}
}
w[start] = false;
int u = U[start];
int v = V[start];
vector<int> neighbors[N];
vector<int> out_edges[N];
for(int i = 0; i < M; i++){
neighbors[U[i]].push_back(V[i]);
neighbors[V[i]].push_back(U[i]);
out_edges[U[i]].push_back(i);
out_edges[V[i]].push_back(i);
}
vector<int> distances_u;
vector<vector<int> > path_edges_u;
vector<int> distances_v;
vector<vector<int> > path_edges_v;
tie(distances_u, path_edges_u) = distances(N, neighbors, out_edges, u);
tie(distances_v, path_edges_v) = distances(N, neighbors, out_edges, v);
int s = search_endpoint(N, M, u, w, distances_u, path_edges_u, distances_v, distance);
int t = search_endpoint(N, M, v, w, distances_v, path_edges_v, distances_u, distance);
answer(s, t);
}
