#include "highway.h"
#include <bits/stdc++.h>
#define uwu return
using namespace std;
#define fs first
#define sc second
int M;
const int SIZE = 9e4 + 4;
vector <int> graph[SIZE];
long long original_dist;
map<pair<int, int>, int> edge_id;
bool query_edges(vector <pair<int, int>> edges){
vector<int> w(M);
for (int i = 0; i < M; ++i) {
w[i] = 0;
}
for(auto i:edges){
if(!edge_id.count(i))
continue;
w[edge_id[i]] = 1;
}
return ask(w) != original_dist;
}
map <int, int> parent, order;
int cnt;
void get_dfs_order(int nd, int pa){
parent[nd] = pa;
cnt++;
order[cnt] = nd;
for(auto i:graph[nd]){
if(i != pa){
get_dfs_order(i, nd);
}
}
return;
}
int find_rooted_tree_stuff(int nd, int pa){
parent.clear(), order.clear();
cnt = 0;
get_dfs_order(nd, pa);
int ret = nd;
for (int L = 1, R = cnt, M; L != R;){
M = (L + R + 1) / 2;
vector <pair<int, int>> block;
for (int i = M; i <= cnt; i++){
block.push_back({order[i], parent[order[i]]});
}
if(query_edges(block)){
L = M;
}
else{
R = M - 1;
}
ret = order[L];
}
return ret;
}
pair <int, int> find_split_edge(int M, vector <int> &U, vector <int> &V){
int ret = 0;
for (int l = 0, r = M - 1, m; l != r;){
m = (l + r + 1) / 2;
vector <pair<int, int>> block;
for (int i = m; i < M; i++){
block.push_back({U[i], V[order[i]]});
}
if(query_edges(block)){
l = m;
}
else{
r = m - 1;
}
ret = l;
}
return {U[ret], V[ret]};
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
M = U.size();
vector<int> w(M);
for (int i = 0; i < M; ++i) {
w[i] = 0;
}
original_dist = ask(w);
for (int i = 0; i < M; i++){
edge_id[{U[i], V[i]}] = i;
edge_id[{V[i], U[i]}] = i;
graph[U[i]].push_back(V[i]);
graph[V[i]].push_back(U[i]);
}
pair<int, int> split = find_split_edge(M, U, V);
int s = find_rooted_tree_stuff(split.fs, split.sc), t = find_rooted_tree_stuff(split.sc, split.fs);
answer(s, t);
uwu;
}
