#include <bits/stdc++.h>
using namespace std;
#include "highway.h"
typedef long long ll;
const int MX = 9e4 + 5;
vector<int> adj[MX], q, t;
int l[MX], r[MX], a, b, n, m, comp[MX];
int findEdge() {
int lo = 0, hi = m - 1, e;
ll base = ask(q);
while(lo <= hi) {
int mid = lo + hi >> 1;
for(int i = 0; i < m; ++i)
q[i] = i <= mid;
if(ask(q) != base)
e = mid, hi = mid - 1;
else lo = mid + 1;
}
return e;
}
void bfs(int root, vector<int> &d, int c, bool store = 0) {
queue<int> Q;
d[root] = 0;
Q.push(root);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int i : adj[u]) {
int v = u ^ l[i] ^ r[i];
if(comp[v] == c && d[v] == -1) {
d[v] = d[u] + 1;
Q.push(v);
if(store) t.push_back(i);
}
}
}
}
int find(int c, vector<int> &d) {
sort(t.begin(), t.end(), [&](int i, int j) {
return max(d[l[i]], d[r[i]]) < max(d[l[j]], d[r[j]]);
});
q = vector<int> (m, 0);
for(int i : t) q[i] = 1;
ll base = ask(q);
int lo = 0, hi = (int) t.size() - 1, e;
while(lo <= hi) {
int mid = lo + hi >> 1;
q = vector<int> (m, 0);
for(int i = 0; i <= mid; ++i)
q[t[i]] = 1;
if(ask(q) == base)
e = t[mid], hi = mid - 1;
else lo = mid + 1;
}
return d[l[e]] > d[r[e]] ? l[e] : r[e];
}
void find_pair(int _n, vector<int> U, vector<int> V, int _a, int _b) {
n = _n, a = _a, b = _b;
m = U.size();
copy(U.begin(), U.end(), l);
copy(V.begin(), V.end(), r);
for(int i = 0; i < m; ++i) {
adj[l[i]].push_back(i);
adj[r[i]].push_back(i);
}
q = vector<int> (m, 0);
int e = findEdge();
vector<int> du (n, -1), dv (n, -1);
bfs(l[e], du, 0);
bfs(r[e], dv, 0);
for(int i = 0; i < n; ++i) {
comp[i] = du[i] > dv[i];
}
du = vector<int> (n, -1);
bfs(l[e], du, 0, 1);
int S = t.size() ? find(0, du) : l[e];
t.clear();
dv = vector<int> (n, -1);
bfs(r[e], dv, 1, 1);
int T = t.size() ? find(0, dv) : r[e];
answer(S, T);
}
