#include "highway.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 10;
vector<pii> G[N];
int E[N], dep[N];
void DFS(int u, int p, int d){
//vis.pb(u);
dep[u] = d;
for(auto [adj, id] : G[u]){
if(adj == p) continue;
E[adj] = id;
DFS(adj, u, d + 1);
}
}
void find_pair(int _n, vector<int> U, vector<int> V, int A, int B){
int n = _n;
int m = U.size();
assert(m == n - 1);
for(int i = 0; i < m; i++){
G[U[i]].pb({V[i], i});
G[V[i]].pb({U[i], i});
}
vector<int> W(m, 0);
ll dis = ask(W);
DFS(0, -1, 0);
vector<int> I(n);
iota(all(I), 0);
sort(all(I), [&](int i, int j){
return dep[i] > dep[j];
});
/*
cerr << "^ ";
for(auto x : I)
cerr << x << ' ';
cerr << '\n';
*/
int st = -1, fn = -1;
int L = 0, R = n - 1;
while(L + 1 < R){
int mid = (L + R) >> 1;
for(int i = 0; i < m; i++) W[i] = 0;
for(int i = 0; i < mid; i++) W[E[I[i]]] = 1;
if(ask(W) > dis) R = mid;
else L = mid;
}
st = I[L];
//cerr << "! " << st << ' ' << L << '\n';
DFS(st, -1, 0);
iota(all(I), 0);
sort(all(I), [&](int i, int j){
return dep[i] > dep[j];
});
L = 0, R = n - 1;
while(L + 1 < R){
int mid = (L + R) >> 1;
for(int i = 0; i < m; i++) W[i] = 0;
for(int i = 0; i < mid; i++) W[E[I[i]]] = 1;
if(ask(W) > dis) R = mid;
else L = mid;
}
fn = I[L];
answer(st, fn);
}
