#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll , ll> ii;
#define ff first
#define ss second
#define pb push_back
const ll N = 1e5 + 5;
vector < ii > v[N];
ii edge[N]; ll in[N]; ll par[N];
ll n, m;
vector < ll > all;
void dfs(ll s, ll p){
par[s] = p;
for(auto [u, i] : v[s]){
if(u - p){
dfs(u, s);
in[i] = all.size();
all.pb(i);
edge[i] = {s, u};
}
}
return;
}
ll query(ll l, ll r){
vector < int > w(m, 0);
for(ll i = l; i <= r; i++) w[all[i]] = 1;
return ask(w);
}
vector < ll > collect;
void DFS(ll s, ll p){
for(auto [u, i] : v[s]){
if(u - p){
DFS(u, s);
collect.pb(i);
}
}
return;
}
void find_pair(int _n, std::vector<int> U, std::vector<int> V, int A, int B) {
n = _n, m = U.size();
for(ll i = 0; i < m; i++){
ll x = V[i], y = U[i];
v[x].pb({y, i});
v[y].pb({x, i});
}
dfs(0, -1);
ll cost = query(0, m-1);
ll lo = 0, hg = m - 1;
ll X = 0, root = 0, Y = 0;
while(lo <= hg){
ll mid = (lo + hg)/2;
ll k = query(0, mid);
if(k == cost){
lo = mid + 1;
}else{
X = mid;
hg = mid - 1;
}
}
lo = 0, hg = m - 1;
while(lo <= hg){
ll mid = (lo + hg)/2;
ll k = query(mid, m-1);
if(k == cost){
hg = mid - 1;
}else{
root = mid;
lo = mid + 1;
}
}
//return;
ll _X = edge[all[X]].ss;
ll _R = edge[all[root]].ff;
DFS(edge[all[root]].ss, _R);
sort(collect.begin(), collect.end());
ll L = collect[0], R = collect.back();
lo = L, hg = R;
while(lo <= hg){
ll mid = (lo + hg)/2;
ll k = query(L, mid);
if(k == cost){
lo = mid + 1;
}else{
hg = mid - 1;
Y = mid;
}
}
ll _Y = edge[all[Y]].ss;
int S,T;
if(_X == _Y) S = _X, T = _R;
else S = _X, T = _Y;
// cout << _X << ' ' << _R << ' ' << _Y << '\n';
answer(S, T);
return;
}
