#include "highway.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
std::vector<int> bfs(int s, const std::vector<std::vector<std::pair<int, int>>>& adj) {
int N = adj.size();
std::vector<int> d(N, -1);
std::queue<int> q;
q.push(s);
d[s] = 0;
while (q.size()) {
int u = q.front();
q.pop();
for (auto [v, id] : adj[u]) {
if (d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
return d;
}
std::vector<std::pair<int, int>> build_tree(int s, const std::vector<std::vector<std::pair<int, int>>>& adj, const std::vector<int>& d1, const std::vector<int>& d2) {
int N = adj.size();
std::vector<std::pair<int, int>> tree;
std::vector<int> d(N, -1);
std::queue<int> q;
q.push(s);
d[s] = 0;
while (q.size()) {
int u = q.front();
q.pop();
for (auto [v, id] : adj[u]) {
if (d1[v] < d2[v] && d[v] == -1) {
tree.emplace_back(v, id);
d[v] = d[u] + 1;
q.push(v);
}
}
}
return tree;
}
int solve(int s, int M, long long sd, const std::vector<std::pair<int, int>>& trees) {
int ans = s, lb = 0, rb = trees.size() - 1;
while (lb <= rb) {
int m = (lb + rb) / 2;
std::vector<int> w(M, 0);
for (int j = m; j < (int) trees.size(); j++) {
w[trees[j].second] = 1;
}
auto res = ask(w);
if (res != sd) {
ans = trees[m].first;
lb = m + 1;
} else {
rb = m - 1;
}
}
return ans;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
std::vector<std::vector<std::pair<int, int>>> adj(N);
int M = U.size();
for (int i = 0; i < M; i++) {
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
auto shortest_distance = ask(std::vector<int>(M, 0));
int first_in_path = -1;
int lb = 0, rb = M - 1;
while (lb <= rb) {
int m = (lb + rb) / 2;
auto nice = std::vector<int>(M, 0);
std::fill(nice.begin(), nice.begin() + m + 1, 1);
auto aa = ask(nice);
if (aa != shortest_distance) {
first_in_path = m;
rb = m - 1;
} else {
lb = m + 1;
}
}
auto a = U[first_in_path];
auto b = V[first_in_path];
auto d1 = bfs(a, adj);
auto d2 = bfs(b, adj);
auto treea = build_tree(a, adj, d1, d2);
std::set<int> fff;
for (auto [x, y] : treea) fff.insert(y), assert(y != first_in_path);
auto treeb = build_tree(b, adj, d2, d1);
for (auto [x, y] : treeb) {
assert(!fff.count(y));
assert(y != first_in_path);
}
auto ff = solve(a, M, shortest_distance, treea);
auto ee = solve(b, M, shortest_distance, treeb);
answer(ff, ee);
}
