#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(x);
dfs(e.u, x);
vt.push_back(e.u);
order.push_back(e.id);
}
}
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, 0));
int l = 0, r = order.size();
while (r-l > 1) {
int mid = (l+r)/2;
vector<int> q(m);
for (int i = 0; i < mid; i++)
q[order[i]]++;
for (int& i : q) {
if (i == 2) i = 1;
else i = 0;
}
ll cost = ask(q);
if (cost == total_cost) l = mid;
else r = mid;
}
int old_l = l;
l = 0, r = (int)order.size();
while (r-l > 1) {
int mid = (l+r)/2;
vector<int> q(m);
for (int i = mid; i < (int)order.size(); i++)
q[order[i]]++;
for (int& i : q) {
if (i == 2) i = 1;
else i = 0;
}
ll cost = ask(q);
if (cost == total_cost) r = mid;
else l = mid;
}
r = l;
l = old_l;
// for (int i : order) cout << i << " ";
// cout << "\n";
// cout << l << " " << r << "\n";
vector<int> cnt(n);
for (int i = l; i <= r; i++) {
cnt[U[order[i]]]++;
cnt[V[order[i]]]++;
}
a = -1, b = -1;
for (int i = 0; i < n; i++) {
if (cnt[i] == 1) {
if (a == -1) a = i;
else b= i;
}
}
if (a > b) swap(a, b);
answer(a, b);
}
