#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const int MAXN = 1e6 + 10;
int from[MAXN], to[MAXN], n, m, par[MAXN];
vector<int> adj[MAXN], dfs_order;
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) {
vector<int> W(m);
for (int e : vec)
W[e] = 1;
return ask(W);
}
inline int get(int l, int r) {
return get(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;
int mx = get(l, r);
for (int e : dfs_order) cerr << e << sep;
cerr << endl;
while (l < r) {
int mid = (l + r) >> 1;
if (get(1, mid) == mx) r = mid;
else l = mid + 1;
}
return dfs_order[l];
}
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 < n - 1; i++) {
from[i] = U[i];
to[i] = V[i];
adj[from[i]].push_back(i);
adj[to[i]].push_back(i);
}
int v = find(0);
int u = find(v);
answer(u, v);
}
