#include "highway.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
int M = U.size();
vector<vector<ii>> adj(N);
for (int i = 0; i < M; i++)
{
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
int64_t all_b = ask(vector<int>(M, 1)),
all_a = all_b / B * A;
int lo = -1, hi = M - 1;
while (hi - lo > 1)
{
int mid = (lo + hi) >> 1;
vector<int> orz(M, 0);
for (int i = 0; i <= mid; i++)
orz[i] = 1;
if (ask(orz) != all_a)
hi = mid;
else
lo = mid;
}
int X = U[hi], Y = V[hi], S, T;
vector<int> depthX(N, INT_MAX), depthY(N, INT_MAX);
if (1)
{
queue<int> q;
q.push(X);
depthX[X] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
for (auto [v, idx] : adj[u])
if (depthX[v] == INT_MAX)
{
depthX[v] = depthX[u] + 1;
q.push(v);
}
}
}
queue<int> q;
q.push(Y);
depthY[Y] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
for (auto [v, idx] : adj[u])
if (depthY[v] == INT_MAX)
{
depthY[v] = depthY[u] + 1;
q.push(v);
}
}
vector<int> based(M, 0);
vector<int> lisX, lisY;
for (int i = 0; i < N; i++)
if (depthX[i] != depthY[i])
{
if (depthX[i] < depthY[i])
lisX.emplace_back(i);
else
lisY.emplace_back(i);
}
for (int i = 0; i < M; i++)
if ((depthX[U[i]] < depthY[U[i]] and depthX[V[i]] > depthY[V[i]]) or
(depthX[U[i]] > depthY[U[i]] and depthX[V[i]] < depthY[V[i]]))
based[i] = 1;
based[hi] = 0;
for (int i = 0; i < N; i++)
if (depthX[i] == depthY[i])
for (auto [v, idx] : adj[i])
based[idx] = 1;
sort(lisX.begin(), lisX.end(), [&](int x, int y)
{ return depthX[x] > depthX[y]; });
sort(lisY.begin(), lisY.end(), [&](int x, int y)
{ return depthY[x] > depthY[y]; });
if (1)
{
int lo = -1, hi = lisX.size() - 1;
while (hi - lo > 1)
{
int mid = (lo + hi) >> 1;
vector<int> orz = based;
for (int i = 0; i <= mid; i++)
for (auto [v, idx] : adj[lisX[i]])
orz[idx] = 1;
if (ask(orz) != all_a)
hi = mid;
else
lo = mid;
}
S = lisX[hi];
}
if (1)
{
int lo = -1, hi = lisY.size() - 1;
while (hi - lo > 1)
{
int mid = (lo + hi) >> 1;
vector<int> orz = based;
for (int i = 0; i <= mid; i++)
for (auto [v, idx] : adj[lisY[i]])
orz[idx] = 1;
if (ask(orz) != all_a)
hi = mid;
else
lo = mid;
}
T = lisY[hi];
}
answer(S, T);
}
