#include "bits/extc++.h"
using namespace std;
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t;
((cerr << " | " << u), ...);
cerr << endl;
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
using ll = long long;
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
inline void init_io() {
cin.tie(nullptr);
cin.exceptions(ios::failbit);
ios_base::sync_with_stdio(false);
}
template <typename T>
vector<T> iota(int n, T x) {
vector<T> ans(n);
iota(begin(ans), end(ans), x);
return ans;
}
template <typename T>
vector<T>& operator+=(vector<T>& a, const vector<T>& b) {
a.insert(end(a), begin(b), end(b));
return a;
}
template <typename T>
vector<T> operator+(vector<T> a, const vector<T>& b) {
return a += b;
}
template <typename Cb>
struct CmpByKey {
Cb cb;
CmpByKey(Cb cb) : cb(cb) {}
template <typename T>
bool operator()(const T& a, const T& b) const {
return cb(a) < cb(b);
}
};
template <typename T, typename Cb>
T first_true(T l, T r, const Cb& cb) {
while (l < r) {
T mid = (l + r) / 2;
if (cb(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
template <typename T, typename Cb>
T last_true(T l, T r, const Cb& cb) {
while (l < r) {
T mid = (l + r + 1) / 2;
if (cb(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
out << "[";
for (int i = 0; i < sz(arr); i++) {
if (i) {
out << ", ";
}
out << arr[i];
}
return out << "]";
}
template <typename T>
T negated(T arr) {
for (auto& a : arr) {
a = -a;
}
return arr;
}
ll ask(const std::vector<int>& w);
void answer(int s, int t);
vector<int> bfs(const vector<vector<pair<int, int>>>& graph, int src) {
int n = sz(graph);
vector dist(n, -1);
queue<int> q;
auto push = [&](int u, int d) -> void {
if (dist[u] != -1) {
return;
}
dist[u] = d;
q.push(u);
};
push(src, 0);
while (sz(q)) {
int u = q.front();
q.pop();
for (auto& [v, _ei] : graph[u]) {
push(v, dist[u] + 1);
}
}
return dist;
}
void solve(int n, const vector<pair<int, int>>& edges, int wa, int) {
int m = sz(edges);
dbg(m);
vector<vector<pair<int, int>>> graph(n);
for (int i = 0; i < m; i++) {
auto& [u, v] = edges[i];
graph[u].emplace_back(v, i);
graph[v].emplace_back(u, i);
}
long base = ask(vector<int>(m, 0));
auto nodes_blocked = [&](const vector<int>& nodes) -> vector<int> {
vector<int> cv(m);
for (auto& u : nodes) {
for (auto& [_v, ei] : graph[u]) {
cv[ei] = true;
}
}
return cv;
};
auto ask_nodes = [&](const vector<int>& nodes) -> bool {
return ask(nodes_blocked(nodes)) > base;
};
int root = first_true(0, n, [&](int x) -> bool {
return ask_nodes(iota(x + 1, 0));
});
dbg(root);
auto base_block = iota(root, 0);
dbg(base_block);
auto dist = bfs(graph, root);
auto ord = iota(n, 0);
sort(begin(ord), end(ord), CmpByKey([&](int u) -> int {
return dist[u];
}));
vector<int> subtree_id(n);
for (auto& a : ord) {
if (a <= root) {
continue;
}
if (dist[a] == 1) {
subtree_id[a] = a;
continue;
}
for (auto& [v, _ei] : graph[a]) {
if (dist[v] == dist[a] - 1 && v >= root) {
subtree_id[a] = subtree_id[v];
}
}
}
int u1_ind = last_true(0, n,
[&](int x) -> bool {
return ask_nodes(base_block + vector(begin(ord) + x, end(ord)));
}),
u1 = ord[u1_ind];
if (dist[u1] == base / wa) {
answer(u1, root);
return;
}
vector<int> rem_nodes;
for (auto& a : ord) {
if (a > root && subtree_id[a] != subtree_id[u1]) {
rem_nodes.push_back(a);
}
}
dbg(subtree_id);
int u2_ind = last_true(0, sz(rem_nodes),
[&](int x) -> bool {
return ask_nodes(base_block +
vector(begin(rem_nodes) + x, end(rem_nodes)));
}),
u2 = rem_nodes[u2_ind];
dbg(u1, u2);
dbg(ord, u1_ind, u2_ind);
answer(u1, u2);
}
void find_pair(int n,
vector<int> edges_u,
vector<int> edges_v,
int wa,
int wb) {
return solve(n, [&]() {
vector<pair<int, int>> cv;
for (int i = 0; i < sz(edges_u); i++) {
cv.emplace_back(edges_u[i], edges_v[i]);
}
return cv;
}(), wa, wb);
}
