#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];
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 : adjlist[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 : adjlist[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;
}
dfs1(0, -1);
/*
for (int i = 0; i < N; ++i) cout << pre1[i] << ' ';
cout << '\n';
*/
int lo = 1; int hi = N-1; int S = unpre1[0];
while (lo <= hi) {
int mid = (lo + hi) / 2;
vector<int> att(M);
for (int i = N-1; i > mid; --i) {
int x = unpre1[i]; ii edge = ii{min(pa1[x], x), max(pa1[x], x)};
att[edgeToIdx[edge]] = 1;
}
ll res = ask(att);
if (res == opt) {
S = unpre1[mid];
hi = mid - 1;
}
else lo = mid + 1;
}
dfs2(S, -1);
/*
for (int i = 0; i < N; ++i) cout << pre2[i] << ' ';
cout << '\n';
for (int i = 0; i < N; ++i) cout << pa2[i] << ' ';
cout << '\n';
*/
lo = 1; hi = N-1; int T = unpre2[0];
while (lo <= hi) {
int mid = (lo + hi) / 2;
vector<int> att(M);
for (int i = N-1; i > mid; --i) {
int x = unpre2[i]; ii edge = ii{min(pa2[x], x), max(pa2[x], x)};
att[edgeToIdx[edge]] = 1;
}
ll res = ask(att);
if (res == opt) {
S = unpre2[mid];
hi = mid - 1;
}
else lo = mid + 1;
}
answer(S, T);
}
/*
4
3
1
3
1
3
0
1
0
2
0
3
*/
