#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long llint;
typedef pair <int, int> pi;
typedef vector <int> vi;
const int MAXN = 90005;
const int MAXM = 150005;
llint n, m, a, b, L, cnt;
int ea[MAXM], eb[MAXM], ok[MAXM];
int bio[MAXN], par[MAXN], pe[MAXN];
vector <pi> v[MAXN], nodes;
vector <int> nula, jen, edges, ch[MAXN];
queue <int> q;
llint pitaj (vi e) {
vi q(m);
for (auto i : e) q[i] = 1;
return ask(q);
}
llint get_length () {
vector <int> e;
return pitaj(e);
}
int find_edge (vi curr) {
int siz = curr.size();
if (siz == 1) return curr[0];
vi lo, hi;
for (int i = 0; i < siz; i++) {
if (2 * i < siz) lo.push_back(curr[i]); else hi.push_back(curr[i]);
}
edges.clear();
for (auto i : jen) edges.push_back(i);
for (auto i : lo) edges.push_back(i);
if (pitaj(edges) == L) {
for (auto i : lo) jen.push_back(i);
return find_edge(hi);
} else {
for (auto i : hi) nula.push_back(i);
return find_edge(lo);
}
}
void bfs (int ra, int rb) {
edges.clear();
memset(bio, -1, sizeof bio);
bio[ra] = bio[rb] = 0;
par[ra] = par[rb] = -1;
q.push(ra); q.push(rb);
while (!q.empty()) {
int x = q.front();
q.pop();
for (auto pp : v[x]) {
int sus = pp.first, ind = pp.second;
if (bio[sus] == -1) {
ch[x].push_back(sus);
par[sus] = x;
pe[sus] = ind;
bio[sus] = 1 + bio[x];
q.push(sus);
}
}
}
for (int i = 0; i < n; i++) {
if (par[i] != -1) ok[pe[i]] = 1;
}
}
void dfs (int x, int rod) {
cnt++;
nodes.push_back({bio[x], x});
for (auto sus : ch[x]) {
dfs(sus, x);
}
}
int solve_subtree (int root, int rod) {
cnt = 0;
dfs(root, rod);
sort(nodes.begin(), nodes.end());
int lo = 0, hi = cnt - 1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
edges.clear();
for (int i = 0; i < m; i++) {
if (!ok[i]) edges.push_back(i);
}
for (int i = mid; i < cnt; i++) {
int node = nodes[i].second;
edges.push_back(pe[node]);
}
if (pitaj(edges) > L) {
lo = mid;
} else {
hi = mid - 1;
}
}
return nodes[lo].second;
}
void find_pair (int N, vi U, vi V, int A, int B) {
n = N; m = U.size(), a = A, b = B;
for (int i = 0; i < m; i++) {
ea[i] = U[i], eb[i] = V[i];
v[U[i]].push_back({V[i], i});
v[V[i]].push_back({U[i], i});
}
L = get_length();
vi curr_edges;
for (int i = 0; i < m; i++) curr_edges.push_back(i);
int ind = find_edge(curr_edges);
ok[ind] = 1;
bfs(ea[ind], eb[ind]);
int sola = solve_subtree(ea[ind], eb[ind]);
int solb = solve_subtree(eb[ind], ea[ind]);
answer(sola, solb);
}
