#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
#define MAX_N 90004
int n;
vector <pair <int ,int>> adj[MAX_N];
vector <pair <int ,int>> edges;
int depth[MAX_N];
vector <int> atdep[MAX_N];
void dfs(int u ,int p ,int d=1){
depth[u] = d;
for(auto v : adj[u]) if(v.first != p){
atdep[d].push_back(v.second);
dfs(v.first ,u ,d+1);
}
}
int solve(int u ,int v ,long long dist){
memset(depth ,0 ,sizeof depth);
for(int i=0; i<MAX_N; i++)
atdep[i].clear();
dfs(u ,v);
int st = 1 ,en = (*max_element(depth ,depth+n))-1 ,mid;
while(st <= en){
mid = (st+en)>>1;
vector <int> w(n-1 ,0);
for(int i : atdep[mid])
w[i] = 1;
if(ask(w) != dist)
st = mid+1;
else
en = mid-1;
}
vector <int>&eds = atdep[--st];
st = 0 ,en = eds.size()-1 ,mid;
while(st < en){
mid = (st+en)>>1;
vector <int> w(n-1 ,0);
for(int i=st; i<=mid; i++)
w[eds[i]] = 1;
if(ask(w) != dist)
en = mid;
else
st = mid+1;
}
if(en == -1)
return u;
u = edges[eds[en]].first ,v = edges[eds[en]].second;
return depth[u] > depth[v] ? u : v;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N;
assert(U.size() == N-1);
for(int i=0; i<N-1; i++)
adj[U[i]].push_back({V[i] ,i}),
adj[V[i]].push_back({U[i] ,i}),
edges.push_back({U[i] ,V[i]});
long long dist = ask(vector<int>(n-1 ,0));
int st = 0 ,en = n-1 ,mid;
while(st < en){
mid = (st+en)>>1;
vector <int> w(n-1 ,0);
for(int i=st; i<=mid; i++)
w[i] = 1;
if(ask(w) != dist)
en = mid;
else
st = mid+1;
}
int s = solve(U[en] ,V[en] ,dist);
int t = solve(V[en] ,U[en] ,dist);
answer(s ,t);
}
