#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e6 + 10;
bool bad[MAXN];
int askcnt = 0;
int from[MAXN], to[MAXN], n, m, par[MAXN], mn;
vector<int> adj[MAXN], dfs_order, fuck;
inline int f(int ind, int v) {
return from[ind] ^ to[ind] ^ v;
}
void dfs(int v, int p) {
dfs_order.push_back(v);
for (int ind : adj[v]) {
int u = f(ind, v);
if (u == p) continue;
if (bad[u]) continue;
par[u] = ind;
dfs(u, v);
}
}
inline vector<int> seg(int l, int r) {
vector<int> ans;
for (int i = l; i <= r; i++)
ans.push_back(par[dfs_order[i]]);
return ans;
}
inline int get(vector<int> vec) {
askcnt++;
assert(askcnt <= 90);
vector<int> W(m);
for (int i = 0; i < m; i++) W[i] = 1;
for (int e : fuck)
W[e] = 0;
for (int e : vec)
W[e] = 1;
return ask(W);
}
inline int getp(vector<int> vec) {
askcnt++;
assert(askcnt <= 90);
vector<int> W(m);
for (int i = 0; i < m; i++)
W[i] = 1;
for (int e : vec)
W[e] = 0;
return ask(W);
}
inline int get(int l, int r) {
return get(seg(l, r));
}
inline int getp(int l, int r) {
return getp(seg(l, r));
}
inline int find(int root) {
par[root] = -1;
dfs_order.clear();
dfs(root, root);
int l = 1, r = int(dfs_order.size()) - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (getp(1, mid) == mn) r = mid;
else l = mid + 1;
}
return dfs_order[l];
}
int dist[MAXN];
const double Z = 0.5;
int fucking_root;
inline vector<int> random_spt() {
vector<int> ans;
queue<int> q;
int l = 0, r = n - 1;
while (l < r) {
int len = r - l;
int mid = l + Z * len;
mid = max(mid, l);
mid = min(mid, r - 1);
vector<int> W(m);
for (int i = 0; i < m; i++)
if (from[i] <= mid || to[i] <= mid)
W[i] = 1;
if (ask(W) == mn) {
for (int i = l; i <= mid; i++) bad[i] = true;
l = mid + 1;
} else r = mid;
}
int v = l;
fucking_root = v;
memset(dist, 63, sizeof dist);
q.push(v);
dist[v] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
if (v < fucking_root) continue;
for (int ind : adj[v]) {
int u = f(ind, v);
if (u < fucking_root) continue;
if (dist[u] > dist[v] + 1) {
dist[u] = dist[v] + 1;
q.push(u);
ans.push_back(ind);
}
}
}
return ans;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
m = U.size();
n = N;
for (int i = 0; i < m; i++) {
from[i] = U[i];
to[i] = V[i];
adj[from[i]].push_back(i);
adj[to[i]].push_back(i);
}
for (int i = 0; i < m; i++)
fuck.push_back(i);
mn = get({});
vector<int> tmp = random_spt();
fuck = tmp;
for (int i = 0; i < n; i++) adj[i].clear();
for (int ind : tmp) {
adj[from[ind]].push_back(ind);
adj[to[ind]].push_back(ind);
}
int v = find(fucking_root);
int u = find(v);
cerr << u << sep << v << endl;
answer(u, v);
}
