#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
vector<vector<int>> adj(n);
int m = u.size();
for (int i = 0; i < m; ++i)
adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
vector<int> in(n);
vector<int> dfs_ord;
int s = -1;
int t = 0;
function<void(int, int)> dfs = [&](int node, int par) {
dfs_ord.push_back(node);
in[node] = t++;
for (auto v : adj[node]) {
if (v == par) continue;
if (v == s) continue;
dfs(v, node);
}
};
dfs(0, -1);
// subgraph w. only verts with in[i] < t
// t = tl -> len ineq.
// t = th -> len eq.
int tl = 0, th = t;
vector<int> hl(m, 0);
int64_t req_d = ask(hl);
while (tl + 1 < th) {
int tm = (tl + th) / 2;
for (int i = 0; i < m; ++i) {
hl[i] = in[u[i]] >= tm || in[v[i]] >= tm;
}
if (ask(hl) == req_d) {
th = tm;
} else {
tl = tm;
}
}
s = dfs_ord[tl];
dfs_ord.clear();
in.assign(n, -1);
t = 0;
dfs(s, -1);
hl.assign(m, 1);
tl = 0, th = t;
req_d = ask(hl);
while (tl + 1 < th) {
int tm = (tl + th) / 2;
for (int i = 0; i < m; ++i) {
hl[i] = in[u[i]] < tm && in[v[i]] < tm;
}
if (ask(hl) == req_d) {
th = tm;
} else {
tl = tm;
}
}
t = dfs_ord[tl];
answer(s, t);
}
#ifndef EVAL
#include "grader.cpp"
#endif
