#include "highway.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 150'010;
int len;
vector<pii> adj0[N];
vector<pii> adj1[N];
int n, m;
ll A, B;
ll ask_edge(bool def, vector<int> T)
{
vector<int> vec(m, def);
for (int e : T) {
vec[e] = !def;
}
return ask(vec);
}
ll ask_ver(vector<int> V, int l, int r)
{
vector<int> vec(m, 1);
Loop (i,0,n)
for (auto [_, e] : adj1[i])
vec[e] = 0;
Loop (i,l,r)
for (auto [_, e] : adj1[V[i]])
vec[e] ^= 1;
return ask(vec);
}
ll ask_ver(vector<int> V) { return ask_ver(V, 0, V.size()); }
int bin_search(vector<int> V)
{
int l = 0, r = V.size();
while (r - l > 1) {
int mid = (l+r)/2;
int par = ((ask_ver(V, l, mid) - A*len) / (B - A)) & 1;
if (par)
r = mid;
else
l = mid;
}
return V[l];
}
bool vis[N];
void bfs(int rt0, int rt1, vector<int> &vrt0, vector<int> &vrt1, vector<int> &T)
{
vrt0 = {rt0}; vrt1 = {rt1};
vector<int> *ans[2] = {&vrt0, &vrt1};
vector<pii> vec = {{rt0,0},{rt1,1}};
vis[rt0] = vis[rt1] = 1;
for (int i = 0; i < vec.size(); ++i) {
auto [v, c] = vec[i];
for (auto [u, e] : adj0[v]) {
if (vis[u])
continue;
vis[u] = 1;
ans[c]->push_back(u);
vec.push_back({u,c});
T.push_back(e);
}
}
}
void find_pair(int _N, vector<int> _U, vector<int> _V, int _A, int _B)
{
n = _N; m = _U.size(); A = _A; B = _B;
Loop (e,0,m) {
int v = _V[e], u = _U[e];
adj0[v].push_back({u, e});
adj0[u].push_back({v, e});
}
len = ask_edge(0, {})/A;
vector<int> V1, V2;
{
int l = 0, r = m;
while (r - l > 1) {
int mid = (l+r)/2;
vector<int> vec(mid);
iota(vec.begin(), vec.end(), 0);
if (ask_edge(0, vec) != len*A)
r = mid;
else
l = mid;
}
vector<int> T = {l};
bfs(_U[l], _V[l], V1, V2, T);
for (int e : T) {
int v = _V[e], u = _U[e];
adj1[v].push_back({u, e});
adj1[u].push_back({v, e});
}
assert(ask_ver({}) == A*len);
}
int s = bin_search(V1);
int t = bin_search(V2);
answer(s, t);
}
