#include "highway.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <numeric>
#include <vector>
#include <queue>
typedef long long llong;
const int MAXN = 90000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;
int n, m, a, b;
std::queue <int> q;
std::vector <std::pair <int,int>> g[MAXN];
std::vector <std::pair <int,int>> t1[MAXN];
std::vector <std::pair <int,int>> t2[MAXN];
std::vector <int> edgeU;
std::vector <int> edgeV;
int inTree[MAXN];
bool vis[MAXN];
int par[MAXN];
int find(std::vector <std::pair <int,int>> t[], int root, int cnt, int cnt2)
{
// std::cout << "find: " << root << ' ' << cnt << '\n' << std::flush;
if (cnt == 0)
{
return root;
}
while (!q.empty())
{
q.pop();
}
std::vector <int> order;
q.push(root);
while (!q.empty())
{
int top = q.front();
q.pop();
for (const auto &[u, idx] : t[top])
{
if (u != par[top])
{
order.push_back(idx);
q.push(u);
}
}
}
std::vector <int> w(m);
int l = -1, r = order.size(), mid;
while (l < r - 1)
{
mid = (l + r) / 2;
std::fill(w.begin(), w.end(), 1);
for (int i = 0 ; i <= mid ; ++i)
{
w[order[i]] = 0;
}
llong res = ask(w);
if (res > 1LL * a * cnt + 1LL * b * cnt2) l = mid;
else r = mid;
}
std::fill(w.begin(), w.end(), 1);
for (int i = 0 ; i < order.size() ; ++i)
{
w[order[i]] = 0;
}
llong res = ask(w);
while (res != 1LL * cnt * a + 1LL * cnt2 * b || r == order.size());
assert(r < order.size());
int u = edgeU[order[r]];
int v = edgeV[order[r]];
if (par[v] == u)
{
std::swap(u, v);
}
return u;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
n = N;
m = U.size();
a = A; b = B;
edgeU = U;
edgeV = V;
for (int i = 0 ; i < m ; ++i)
{
g[U[i]].push_back({V[i], i});
g[V[i]].push_back({U[i], i});
}
std::vector <int> toAsk(m, 0);
llong res = ask(toAsk);
int l = -1, r = m, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
std::fill(toAsk.begin(), toAsk.end(), 0);
for (int i = 0 ; i <= mid ; ++i)
{
toAsk[i] = 1;
}
llong curr = ask(toAsk);
if (curr == res) l = mid;
else r = mid;
}
assert(r < m);
int rootOne = U[r];
int rootTwo = V[r];
inTree[rootOne] = 1;
inTree[rootTwo] = 2;
vis[rootOne] = true;
vis[rootTwo] = true;
q.push(rootOne);
q.push(rootTwo);
while (!q.empty())
{
int top = q.front();
q.pop();
for (const auto &[u, idx] : g[top])
{
if (!vis[u])
{
par[u] = top;
vis[u] = true;
inTree[u] = inTree[top];
if (inTree[top] == 1)
{
t1[top].push_back({u, idx});
t1[u].push_back({top, idx});
} else
{
t2[top].push_back({u, idx});
t2[u].push_back({top, idx});
}
q.push(u);
}
}
}
std::fill(toAsk.begin(), toAsk.end(), 0);
for (int i = 0 ; i < n ; ++i)
{
for (const auto &[u, idx] : t1[i])
{
toAsk[idx] = 1;
}
}
std::fill(toAsk.begin(), toAsk.end(), 0);
for (int i = 0 ; i < n ; ++i)
{
for (const auto &[u, idx] : t1[i])
{
toAsk[idx] = 1;
}
}
llong currRES = ask(toAsk);
int cntEdges = (currRES - res) / (b - a);
int cntEdges2 = res / a - cntEdges - 1;
int s = find(t1, rootOne, cntEdges, cntEdges2 + 1);
int t = find(t2, rootTwo, cntEdges2, cntEdges + 1);
answer(s, t);
}
/*
9 12 1 10 1 3
0 1
1 2
2 6
6 3
3 4
4 0
0 5
5 6
6 7
7 0
0 8
8 6
*/
