#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int n = N, m = U.size();
vector <vector<ar<int,2>>> adj(n);
for ( int i = 0; i < m; i++ ){
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
}
vector <int> w(m);
i64 C = ask(w);
int l = 0, r = m - 1;
while ( l < r ){
int md = (l + r) / 2;
w.assign(m, 0);
for ( int i = 0; i <= md; i++ ){
w[i] = 1;
}
if ( ask(w) != C ){
r = md;
} else l = md + 1;
}
vector <vector<ar<int,2>>> tree(n);
auto bfs = [&](int sx){
vector <int> d(n, n + 1);
for ( auto &x: tree ){
x.clear();
}
queue <int> q;
q.push(sx); d[sx] = 0;
while ( !q.empty() ){
int u = q.front();
q.pop();
for ( auto &[v, j]: adj[u] ){
if ( chmin(d[v], d[u] + 1) ){
q.push(v);
tree[u].pb({v, j});
}
}
}
return d;
};
auto d1 = bfs(U[l]); auto g1 = tree;
auto d2 = bfs(V[l]); auto g2 = tree;
int E = l;
auto get = [&](int sx){
vector <int> e, ord;
auto dfs = [&](auto dfs, int u) -> void{
ord.pb(u);
for ( auto &[v, j]: g1[u] ){
if ( d1[v] >= d2[v] ){
continue;
}
e.pb(j);
dfs(dfs, v);
}
};
dfs(dfs, sx);
w.assign(m, 1);
for ( auto &j: e ) w[j] = 0;
w[E] = 0;
i64 T = ask(w);
int l = 0, r = (int)e.size();
while ( l < r ){
int md = (l + r) / 2;
w.assign(m, 1);
for ( int i = 0; i < (int)e.size(); i++ ){
w[e[i]] = !(i < md);
} w[E] = 0;
if ( ask(w) == T ){
r = md;
} else l = md + 1;
}
return ord[l];
};
int x = get(U[l]);
swap(d1, d2), swap(g1, g2);
int y = get(V[l]);
answer(x, y);
}
