#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int const maxn = 90909;
struct Edge {
int u, id;
};
vector<Edge> v[maxn];
vector<int> order;
vector<int> vt;
void dfs(int x, int p) {
for (Edge e : v[x]) {
if (e.u == p) continue;
order.push_back(e.id);
vt.push_back(e.u);
dfs(e.u, x);
order.push_back(e.id);
vt.push_back(x);
}
}
void find_pair(int n, vector<int> U, vector<int> V, int a, int b) {
int m = U.size();
for (int i = 0; i < m; i++) {
v[U[i]].push_back(Edge{V[i], i});
v[V[i]].push_back(Edge{U[i], i});
}
dfs(0, 0);
ll total_cost = ask(vector<int>(m, 1));
int l = 0, r = (int)order.size();
while (r-l > 1) {
int mid = (l+r)/2;
vector<int> q(m, 0);
for (int i = 0; i < mid; i++)
q[order[i]] = 1;
ll cost = ask(q);
if (cost == total_cost) r = mid;
else l = mid;
}
a = vt[l];
r = (int)order.size();
order.clear();
vt.clear();
dfs(a, a);
l = 0, r = (int)order.size();
while (r-l > 1) {
int mid = (l+r)/2;
vector<int> q(m, 0);
for (int i = 0; i < mid; i++)
q[order[i]] = 1;
ll cost = ask(q);
if (cost == total_cost) r = mid;
else l = mid;
}
b = vt[l];
answer(a, b);
}
