#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
map<pair<int, int>, int> id;
vector<int> par, d; vector<vector<int>> adj; vector<pair<int, int>> edges;
long long base = 0;
void dfs(int node, int prev, int dp) {
if (node < 0 || node >= n) return;
par[node] = prev;
d[node] = dp;
for (auto &neighbour : adj[node]) {
if (neighbour == prev) continue;
dfs(neighbour, node, dp + 1);
}
}
void buildpar(int root) {
par.resize(n); d.resize(n);
dfs(root, -1, 0);
}
int ch(int x, int y) {
if (par[x] == y) return x;
else return y;
}
int findlow() {
vector<int> edgeorder;
vector<int> childs(n); for (int i = 0; i < n; i++) {
if (par[i] != -1) childs[par[i]]++;
}
set<pair<int, int>> lf; for (int i = 0; i < n; i++) if (!childs[i]) lf.insert({-d[i], i});
while (lf.size()) {
int cur = (*lf.begin()).second;
lf.erase(lf.begin());
if (par[cur] == -1) break;
edgeorder.push_back(id[{cur, par[cur]}]);
childs[par[cur]]--;
if (!childs[par[cur]]) lf.insert({-d[par[cur]], par[cur]});
}
int lo = -1, hi = n-1;
while (hi > lo + 1) {
int mid = (lo + hi) / 2;
vector<int> w(n - 1); for (int j = 0; j <= mid; j++) w[edgeorder[j]] = 1;
long long q = ask(w);
if (q > base) hi = mid;
else lo = mid;
}
return ch(edges[edgeorder[hi]].first, edges[edgeorder[hi]].second);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size(); assert(M == N - 1);
n = N; m = M; adj.resize(n);
base = ask(vector<int>(M));
for (int i = 0; i < M; i++) {
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
edges.push_back({U[i], V[i]});
id[{U[i], V[i]}] = i;
id[{V[i], U[i]}] = i;
}
buildpar(0); int x = findlow();
buildpar(x); int y = findlow();
answer(x, y);
}
/*
14 13 27 95 7 4
0 1
0 2
0 3
3 4
4 10
4 11
4 12
4 13
3 5
5 6
6 7
7 8
7 9
*/
