#include "highway.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <tuple>
#include <utility>
using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;
using std::begin;
using std::end;
using ll = long long;
constexpr int inf = 1 << 30;
constexpr ll infll = (1ll << 62) - 1;
template <class F> int binary_search(int ok, int ng, const F& f) {
while (std::abs(ok - ng) > 1) {
const int md = (ok + ng) / 2;
(f(md) ? ok : ng) = md;
}
return ok;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
const int M = (int)U.size();
vector<vector<int>> G(N);
for (int i = 0; i < M; ++i) {
G[U[i]].push_back(i);
G[V[i]].push_back(i);
}
const auto bfs_order = [&](int src) {
vector<int> ret;
vector<char> done(N);
std::queue<int> que;
ret.reserve(N);
const auto push = [&](int u) {
if (!done[u]) {
done[u] = true;
ret.push_back(u);
que.push(u);
}
};
push(src);
while (!que.empty()) {
const int u = que.front();
que.pop();
for (const int e : G[u]) {
push(u ^ U[e] ^ V[e]);
}
}
return ret;
};
const ll best = ask(vector(M, 0));
const int P = binary_search(0, N, [&](int thres) -> bool {
vector<int> w(M);
for (int i = 0; i < thres; ++i) {
for (const int e : G[i]) w[e] = 1;
}
return ask(w) == best;
});
const auto ordP = bfs_order(P);
const int S = ordP[binary_search(N, 0, [&](int thres) -> bool {
vector<int> w(M);
for (int i = thres; i < N; ++i) {
for (const int e : G[ordP[i]]) w[e] = 1;
}
return ask(w) == best;
}) - 1];
const auto ordS = bfs_order(S);
const int T = ordS[binary_search(N, 0, [&](int thres) -> bool {
vector<int> w(M);
for (int i = thres; i < N; ++i) {
for (const int e : G[ordS[i]]) w[e] = 1;
}
return ask(w) == best;
}) - 1];
answer(S, T);
}
