#include "highway.h"
#include <bits/stdc++.h>
#define uwu return
using namespace std;
#define fs first
#define sc second
#define all(x) x.begin(), x.end()
int M;
const int SIZE = 9e4 + 4;
vector <int> graph[SIZE];
long long original_dist;
map <pair<int, int>, int> edge_id;
vector <pair<int, int>> always_blocked;
bool query_edges(vector <pair<int, int>> &edges){
vector<int> w(M, 0);
for(auto i:edges){
w[edge_id[i]] = 1;
}
for(auto i:always_blocked){
w[edge_id[i]] = 1;
}
return ask(w) != original_dist;
}
bitset <SIZE> been;
int order[SIZE];
vector <int> in_edge[SIZE];
int dist[SIZE];
int cnt;
void get_BFS_DAG(int nd){
dist[nd] = 0;
queue <int> q;
q.push(nd);
been[nd] = 1;
while (!q.empty()){
int i = q.front();
q.pop();
for (auto j : graph[i]){
if (been[j]){
if(dist[j] == dist[i] + 1)
in_edge[j].push_back(i);
continue;
}
been[j] = 1;
dist[j] = dist[i] + 1;
in_edge[j].push_back(i);
q.push(j);
}
}
uwu;
}
void get_dfs_order(int nd){
cnt++;
order[cnt] = nd;
been[nd] = 1;
for (auto i : graph[nd]){
if(been[i] || dist[i] != dist[nd] + 1){
continue;
}
get_dfs_order(i);
}
return;
}
int find_BFS_DAG_stuff(int nd, int pa){
been.reset();
memset(dist, 0x3f, sizeof(dist));
get_BFS_DAG(nd);
been.reset();
cnt = 0;
get_dfs_order(nd);
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++){
for(auto j:in_edge[order[i]]){
block.push_back({order[i], j});
}
}
if(query_edges(block)){
L = M;
}
else{
R = M - 1;
}
ret = order[L];
}
return ret;
}
pair <int, int> find_split_edge(int M, int N, 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[i]});
}
if(query_edges(block)){
l = m;
}
else{
r = m - 1;
}
ret = l;
}
set <pair<int, int>> ab;
for (int i = ret + 1; i < M; i++){
ab.insert({U[i], V[i]});
ab.insert({V[i], U[i]});
always_blocked.push_back({U[i], V[i]});
}
for (int i = 0; i < N; i++){
vector <int> ng;
for(auto j:graph[i]){
if(ab.count({i, j}))
continue;
ng.push_back(j);
}
graph[i] = ng;
}
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, N, U, V);
// cout << split.fs << ' ' << split.sc << '\n';
int s = find_BFS_DAG_stuff(split.fs, split.sc), t = find_BFS_DAG_stuff(split.sc, split.fs);
// cout << s << ' ' << t << '\n';
answer(s, t);
uwu;
}
