#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/contests/ioi18_d2/debug.h"
#else
#define debug(...) void(37)
#endif
template<typename F = function<bool(const int&)>>
int find_first(int l, int r, F good) {
++r;
int bad = r;
while (l < r) {
int mid = (l + r) >> 1;
if (!good(mid)) {
l = mid + 1;
} else {
r = mid;
}
}
return (l == bad ? -1 : l);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = 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);
}
/*
for (int j = 0; j < 50; ++j) {
std::vector<int> w(M);
for (int i = 0; i < M; ++i) {
w[i] = 0;
}
long long toll = ask(w);
}
answer(0, N - 1);
*/
int64_t small = ask(vector<int>(M, 0));
int on_path = find_first(0, N - 1, [&](int m) {
vector<int> w(M, 0);
for (int i = 0; i <= m; ++i) {
for (auto id : g[i]) w[id] = 1;
}
int64_t g = ask(w);
return g != small;
});
assert(on_path != -1);
debug(on_path);
//you can predetermine if it's S or T but ignore it for now
vector<int> que;
vector<bool> vis(N);
vector<int> par(N, -1);
vis[on_path] = true;
que.push_back(on_path);
vector<int> start_w(M, 1);
for (int it = 0; it < int(que.size()); ++it) {
int v = que[it];
for (auto id : g[v]) {
int u = v ^ V[id] ^ U[id];
if (!vis[u]) {
vis[u] = true;
start_w[id] = 0;
par[u] = v;
vis[u] = true;
que.push_back(u);
}
}
}
auto ord = que;
reverse(ord.begin(), ord.end());
int S = ord[find_first(0, N - 2, [&](int m) {
auto w = start_w;
for (int i = 0; i <= m; ++i) {
for (auto id : g[ord[i]]) w[id] = 1;
}
int64_t g = ask(w);
return g != small;
})];
debug(S);
vector<bool> rem(N);
{
int v = S;
while (v != -1) {
rem[v] = true;
v = par[v];
}
}
{
vector<int> new_ord;
for (auto v : ord) {
if (!rem[v]) {
new_ord.push_back(v);
}
}
swap(ord, new_ord);
}
debug(ord);
int Q_ind = find_first(0, int(ord.size()) - 1, [&](int m) {
auto w = start_w;
for (int i = 0; i <= m; ++i) {
for (auto id : g[ord[i]]) w[id] = 1;
}
int64_t g = ask(w);
return g != small;
});
debug(Q_ind);
if (Q_ind == -1) {
answer(S, on_path);
} else {
answer(S, ord[Q_ind]);
}
}
