#include "highway.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 1e5;
int n, m;
vii graph[MAX_N];
pii par[MAX_N];
int U[MAX_N], V[MAX_N];
vi dist[MAX_N];
bitset<MAX_N> visited;
vi curr_edges;
void Dfs(int node, int parent, int d) {
dist[d].push_back(node);
visited[node] = true;
par[node].x = parent;
for (auto [neighbor, ind] : graph[node]) {
if (neighbor == parent) par[node].y = ind;
else {
curr_edges.push_back(ind);
Dfs(neighbor, node, d + 1);
}
}
}
ll original = 0;
vi edges;
int Solve(int u, int v) {
for (int i = 0; i < n; i++) dist[i].clear();
visited.reset();
curr_edges.clear();
Dfs(u, v, 0);
vi query(m, 1);
for (int i : edges) query[i] = 0;
for (int i : curr_edges) query[i] = 1;
int begin = 0, end = curr_edges.size(), mid;
while (begin < end) {
mid = (begin + end) >> 1;
for (int i = 0; i < mid; i++) {
query[curr_edges[i]] = 0;
}
if (ask(query) != original) begin = mid + 1;
else end = mid;
for (int i = 0; i < mid; i++) {
query[curr_edges[i]] = 1;
}
}
if (!end) return u;
int i = curr_edges[end - 1];
return par[U[i]].x == V[i] ? U[i] : V[i];
}
vii Bfs(int node) {
vii dists(n, {n, -1});
dists[node] = {0, -1};
queue<int> q;
q.push(node);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto [u, i] : graph[v]) {
if (dists[v].x + 1 < dists[u].x) {
dists[u] = {dists[v].x + 1, i};
q.push(u);
}
}
}
return dists;
}
void find_pair(int N, vi U1, vi V1, int A, int B) {
m = U1.size(), n = N;
for (int i = 0; i < m; i++) {
U[i] = U1[i], V[i] = V1[i];
}
for (int i = 0; i < m; i++) {
graph[U[i]].push_back({V[i], i});
graph[V[i]].push_back({U[i], i});
}
original = ask(vi(m));
int begin = 0, end = m, mid;
while (begin < end) {
mid = (begin + end) >> 1;
vi v(m);
fill(v.begin(), v.begin() + mid + 1, 1);
if (ask(v) > original) end = mid;
else begin = mid + 1;
}
int x = V[end], y = U[end];
vii d1 = Bfs(x), d2 = Bfs(y);
d1[x].y = end, d2[y].y = end;
for (int i = 0; i < n; i++) {
if (i == y) continue;
if (d1[i].x < d2[i].x) {
edges.push_back(d1[i].y);
} else if (d1[i].x > d2[i].x){
edges.push_back(d2[i].y);
}
}
for (int i = 0; i < n; i++) graph[i].clear();
vi v(m, 1);
for (int i : edges) {
graph[U[i]].push_back({V[i], i});
graph[V[i]].push_back({U[i], i});
v[i] = 0;
}
answer(Solve(U[end], V[end]), Solve(V[end], U[end]));
}
