#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using pii = pair <int, int>;
using vi = vector <int>;
#define N 200005
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define ll long long
int deep[N], cnt, flat[N], len, curdeep;
vector <pii> edg[N];
pii parent[N];
bool vis[N];
void dfs(int u){
vis[u] = 1;
flat[cnt++] = u;
for (pii v : edg[u])
if (!vis[v.F]){
dfs(v.F);
parent[v.F] = mp(u, v.S);
}
}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
vi v(M);
ll maxdist, dist;
for (int i = 0;i < M;i++) v[i] = 1;
maxdist = ask(v);
for (int i = 0;i < M;i++) v[i] = 0;
for (int i = 0;i < M;i++){
edg[U[i]].pb(mp(V[i], i));
edg[V[i]].pb(mp(U[i], i));
}
dfs(0);
int l = 1, r = n - 1, mid;
while (l != r){
mid = (l + r) / 2;
for (int i = l;i <= mid;i++)
v[parent[flat[i]].S] = 1;
dist = ask(v);
if (dist < maxdist) l = mid + 1;
else {
r = mid;
for (int i = l;i <= mid;i++)
v[parent[flat[i]].S] = 0;
}
}
for (int i = 0;i < M;i++) v[i] = 0;
int s = flat[l];
cnt = 0;
memset(vis, 0, sizeof vis);
dfs(s);
l = 1, r = n - 1;
while (l != r){
mid = (l + r) / 2;
for (int i = l;i <= mid;i++)
v[parent[flat[i]].S] = 1;
dist = ask(v);
if (dist < maxdist) l = mid + 1;
else {
r = mid;
for (int i = l;i <= mid;i++)
v[parent[flat[i]].S] = 0;
}
}
int t = flat[l];
answer(s, t);
}
