#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;
mt19937_64 rd(time(0));
ll ask_edge(vector<int> T)
{
vector<int> vec(m, 1);
for (int e : T) {
vec[e] = 0;
}
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];
bool bad[N];
void dfs(int v, vector<int> &vec)
{
vis[v] = 1;
for (auto [u, _] : adj0[v]) {
if (bad[u])
continue;
vec.push_back(v);
if (vis[u])
continue;
dfs(u, vec);
}
}
void bfs(int rt, vector<int> &T)
{
vector<int> vec = {rt};
vis[rt] = 1;
for (int i = 0; i < vec.size(); ++i) {
int v = vec[i];
for (auto [u, e] : adj0[v]) {
if (bad[u] || vis[u])
continue;
T.push_back(e);
vis[u] = 1;
vec.push_back(u);
}
}
}
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});
}
vector<int> dard(m);
iota(dard.begin(), dard.end(), 0);
len = ask_edge(dard)/A;
for (;;) {
vector<int> T, rts;
memset(vis, 0, sizeof(vis));
Loop (v,0,n) {
if (bad[v] || vis[v])
continue;
vector<int> vec;
dfs(v, vec);
if (vec.size())
rts.push_back(vec[rd()%vec.size()]);
}
memset(vis, 0, sizeof(vis));
for (int rt : rts)
bfs(rt, T);
if (ask_edge(T) == len*A) {
for (auto e : T) {
int v = _V[e], u = _U[e];
adj1[v].push_back({u, e});
adj1[u].push_back({v, e});
}
break;
}
for (int rt : rts)
bad[rt] = 1;
}
vector<int> V;
for (;;) {
V.clear();
Loop (i,0,n)
if (rd()&1)
V.push_back(i);
int par = ((ask_ver(V) - A*len) / (B - A)) & 1;
if (par)
break;
}
int s = bin_search(V);
V.resize(n);
iota(V.begin(), V.end(), 0);
V.erase(V.begin()+s);
int t = bin_search(V);
answer(s, t);
}
