#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
namespace my {
const int N = 1e6 + 10;
struct edge {
int u, i;
edge(int x, int y) : u(x), i(y) {}
operator int() {
return u;
}
};
int bs(vector<int> p) {
auto check = [&](int n) -> ll {
assert(0 <= n && n <= (int)p.size());
vector<int> w(p.size(), 0);
for (int i = 0; i < n; ++i) {
w[p[i]] = 1;
}
return ask(w);
};
int lef = -1, rig = (int)p.size();
ll val = check(rig);
while (rig - lef > 1) {
int mid = (lef + rig) / 2;
if (check(mid) == val) {
rig = mid;
} else {
lef = mid;
}
}
assert(rig - 1 < (int)p.size());
assert(0 <= rig - 1);
return p[rig - 1];
}
vector<edge> g[N];
vector<int> bin, bout;
void dfs(int v, int p) {
for (auto u : g[v]) {
if (u == p) {
continue;
}
bin.push_back(u.i);
dfs(u, v);
bout.push_back(u.i);
}
}
int d[N];
int p[N];
int e[N];
int far(int from, int x, int y) {
queue<int> q;
fill_n(d, N, -1);
d[from] = 0;
q.push(from);
while (q.size()) {
int v = q.front(); q.pop();
for (auto u : g[v]) {
if (d[u] == -1) {
d[u] = d[v] + 1;
q.push(u);
}
}
}
return d[x] > d[y] ? x : y;
}
bool check(int m, int a, int b, int x, int y) {
queue<int> q;
fill_n(d, N, -1);
d[x] = 0;
q.push(x);
while (q.size()) {
int v = q.front(); q.pop();
for (auto u : g[v]) {
if (d[u] == -1) {
d[u] = d[v] + 1;
p[u] = v;
e[u] = u.i;
q.push(u);
}
}
}
int v = y;
vector<int> w(m, 0);
ll d0 = ask(w);
while (v != x) {
int i = e[v];
v = p[v];
w[i] = 1;
}
ll d1 = ask(w);
// cout << "check " << m << " " << a << " " << b << " " << x << " " << y << endl;
// cout << "\t\t" << d0 << " " << d1 << " " << d[y] << endl;
return d0 == a * d[y] && d1 == b * d[y];
}
}
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
using namespace my;
assert(a < b);
int m = (int)u.size();
for (int i = 0; i < m; ++i) {
g[v[i]].emplace_back(u[i], i);
g[u[i]].emplace_back(v[i], i);
}
dfs(0, 0);
int x = bs(bin);
int y = bs(bout);
reverse(all(bout));
int z = bs(bout);
int fi = far(v[y], v[x], u[x]);
int se = far(v[x], v[y], u[y]);
if (check(m, a, b, fi, se)) {
answer(fi, se);
return;
}
fi = far(v[z], v[x], u[x]);
se = far(v[x], v[z], u[z]);
assert(check(m, a, b, fi, se));
answer(fi, se);
}
#ifdef LC
#include "grader.cpp"
#endif
