#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 90'000 + 5;
int pa1[MAXN];
int pre1[MAXN];
int unpre1[MAXN];
int pa2[MAXN];
int pre2[MAXN];
int unpre2[MAXN];
vector<int> adjlist[MAXN];
vector<int> tadjlist[MAXN];
int ctr1 = 0;
int ctr2 = 0;
void dfs1(int x, int pa) {
pre1[x] = ctr1++;
unpre1[pre1[x]] = x;
pa1[x] = pa;
for (int ch : tadjlist[x]) {
if (ch == pa) continue;
dfs1(ch, x);
}
}
void dfs2(int x, int pa) {
pre2[x] = ctr2++;
unpre2[pre2[x]] = x;
pa2[x] = pa;
for (int ch : tadjlist[x]) {
if (ch == pa) continue;
dfs2(ch, x);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
using ii = pair<int, int>;
using ll = long long;
int M = U.size();
ll opt = ask(vector<int>(M, 0));
map<pair<int, int>, int> edgeToIdx;
for (int i = 0; i < M; ++i) {
adjlist[U[i]].emplace_back(V[i]);
adjlist[V[i]].emplace_back(U[i]);
edgeToIdx[ii{min(U[i], V[i]), max(U[i], V[i])}] = i;
}
// bsta for first edge that is on an sssp
int lo = 0; int hi = M-1; int must_use = 0;
while (lo <= hi) {
vector<int> what(M);
int mid = (lo + hi) / 2;
for (int i = 0; i < mid; ++i) what[i] = 1;
if (ask(what) == opt) {
must_use = mid;
lo = mid + 1;
}
else hi = mid - 1;
}
/*
cout << "identified critical edge: " << U[must_use] << ' ' << V[must_use] << '\n';
*/
// make every non-sssp tree edge heavy
vector<int> base(M, 1);
// multi source bfs - construct sssp tree
queue<int> q;
vector<bool> vis(N);
q.emplace(U[must_use]);
q.emplace(V[must_use]);
vis[U[must_use]] = true;
vis[V[must_use]] = true;
tadjlist[U[must_use]].emplace_back(V[must_use]);
tadjlist[V[must_use]].emplace_back(U[must_use]);
base[edgeToIdx[ii{min(U[must_use], V[must_use]), max(U[must_use], V[must_use])}]] = 0;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int ch : adjlist[x]) {
if (vis[ch]) continue;
tadjlist[x].emplace_back(ch);
tadjlist[ch].emplace_back(x);
base[edgeToIdx[ii{min(x, ch), max(x, ch)}]] = 0;
vis[ch] = true;
q.emplace(ch);
}
}
dfs1(U[must_use], V[must_use]);
dfs2(V[must_use], U[must_use]);
/*
cout << "sssp tree constructed:\n";
for (int i = 0; i < ctr1; ++i) cout << unpre1[i] << ' ' << pa1[unpre1[i]] << '\n';
for (int i = 0; i < ctr2; ++i) cout << unpre2[i] << ' ' << pa2[unpre2[i]] << '\n';
*/
lo = 0; hi = ctr1-1; int S = unpre1[0];
while (lo <= hi) {
int mid = (lo + hi) / 2;
for (int i = ctr1-1; i > mid; --i) {
int x = unpre1[i]; ii edge = ii{min(pa1[x], x), max(pa1[x], x)};
base[edgeToIdx[edge]] = 1;
}
for (int i = mid; i >= 0; --i) {
int x = unpre1[i]; ii edge = ii{min(pa1[x], x), max(pa1[x], x)};
base[edgeToIdx[edge]] = 0;
}
/*
for (int i = 0; i < M; ++i) {
cout << U[i] << ' ' << V[i] << ' ' << base[i] << '\n';
}
*/
ll res = ask(base);
if (res == opt) {
S = unpre1[mid];
hi = mid - 1;
}
else lo = mid + 1;
}
// clear subtree 1 from the bsta
for (int i = 0; i < ctr1; ++i) {
int x = unpre1[i]; ii edge = ii{min(pa1[x], x), max(pa1[x], x)};
base[edgeToIdx[edge]] = 0;
}
lo = 0; hi = ctr2-1; int T = unpre2[0];
while (lo <= hi) {
int mid = (lo + hi) / 2;
for (int i = ctr2-1; i > mid; --i) {
int x = unpre2[i]; ii edge = ii{min(pa2[x], x), max(pa2[x], x)};
base[edgeToIdx[edge]] = 1;
}
for (int i = mid; i >= 0; --i) {
int x = unpre2[i]; ii edge = ii{min(pa2[x], x), max(pa2[x], x)};
base[edgeToIdx[edge]] = 0;
}
/*
for (int i = 0; i < M; ++i) {
cout << U[i] << ' ' << V[i] << ' ' << base[i] << '\n';
}
*/
ll res = ask(base);
if (res == opt) {
T = unpre2[mid];
hi = mid - 1;
}
else lo = mid + 1;
}
answer(S, T);
}
/*
4
4
1
3
1
3
1
0
2
0
3
0
1
2
*/
