#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;
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;
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];
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int dist[MAXN];
inline vector<int> random_spt() {
for (int v = 0; v < n; v++)
shuffle(all(adj[v]), rng);
vector<int> ans;
queue<int> q;
int v = rng() % n;
memset(dist, 63, sizeof dist);
q.push(v);
dist[v] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int ind : adj[v]) {
int u = f(ind, v);
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({});
while (true) {
vector<int> tmp = random_spt();
if (getp(tmp) == mn) {
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);
}
break;
}
}
int v = find(0);
int u = find(v);
answer(u, v);
}
