#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define pii pair<int, int>
#define f first
#define s second
#define sz(x) (int)((x).size())
const int siz = 1e6+40;
int nbE;
vector<pii> graph [siz];
int dist [2][siz];
bool incl [2][siz];
int used [2][siz];
int caller(vector<int> where) {
vector<signed> u(nbE, 0);
for (int i : where) {
u[i] = 1; // se heavy
}
int r = ask(u);
return r;
}
void bfs(const int t, int src) {
queue<int> q;
q.push(src);
dist[t][src] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (pii y : graph[x]) {
if (dist[t][y.f] == -1) {
dist[t][y.f] = dist[t][x] + 1;
q.push(y.f);
used[t][y.f] = y.s;
incl[t][y.s] = true;
}
}
}
}
int whoIncrease(vi edgeSet, int refD) {
int x = 0;
for (int i = (1<<20); i; i /= 2) {
int prop = x+i;
if (prop > sz(edgeSet)) continue;
vi where;
for (int j = 0; j < prop; j++) {
where.push_back(edgeSet[j]);
}
int r = caller(where);
assert(r >= refD);
if (r == refD) {
x = prop;
}
}
return edgeSet[x];
}
void find_pair(const signed n, std::vector<signed> edgeX, std::vector<signed> edgeY, signed aK, signed bK) {
for (int i = 0; i < n; i++) graph[i].clear();
nbE = sz(edgeX);
int distVert = caller({});
vi allEdges;
for (int i = 0; i < nbE; i++) {
allEdges.push_back(i);
}
const int magicEdge = whoIncrease(allEdges, distVert);
for (int i = 0; i < nbE; i++) {
graph[edgeX[i]].push_back({edgeY[i], i});
graph[edgeY[i]].push_back({edgeX[i], i});
}
for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++) dist[i][j] = -1;
for (int i = 0; i < nbE; i++) {
incl[0][i] = incl[1][i] = false;
used[0][i] = used[1][i] = -1;
}
bfs(0, edgeX[magicEdge]);
bfs(1, edgeY[magicEdge]);
for (int i = 0; i < n; i++) {
assert(dist[0][i] != -1 && dist[1][i] != -1);
if (dist[0][i] < dist[1][i]) {
dist[1][i] = -1;
}
else {
dist[0][i] = -1;
}
}
// vi between;
// for (int i = 0; i < nbE; i++) if (i != magicEdge) {
// if ((dist[0][edgeX[i]] == -1) != (dist[0][edgeY[i]] == -1)) {
// between.push_back(i);
// }
// }
vi res;
for (int t = 0; t < 2; t++) {
vector<pair<int, int>> cand;
for (int i = 0; i < n; i++) if (dist[t][i] != -1 && used[t][i] != -1) {
cand.push_back({dist[t][i], used[t][i]});
}
set<int> lftEdges;
for (int i = 0; i < nbE; i++) if (i != magicEdge) lftEdges.insert(i);
for (int i = 0; i < n; i++) if (dist[!t][i] != -1 && used[!t][i] != -1) {
lftEdges.erase(used[!t][i]);
}
for (pii i : cand) lftEdges.erase(i.s);
sort(cand.begin(), cand.end());
int bs = -1;
for (int i = (1<<20); i; i /= 2) {
int prop = bs+i;
if (prop >= sz(cand)) continue;
vi where;
for (int j = prop; j < sz(cand); j++) {
where.push_back(cand[j].s);
}
// for (int j : between) {
// where.push_back(j);
// }
for (int j : lftEdges) {
where.push_back(j);
}
int loc = caller(where);
if (loc > distVert) {
bs = prop;
}
}
if (bs == -1 || bs == sz(cand)) {
if (t == 0) {
res.push_back(edgeX[magicEdge]);
}
else {
res.push_back(edgeY[magicEdge]);
}
continue;
}
int loc;
if (dist[t][edgeX[cand[bs].second]] > dist[t][edgeY[cand[bs].second]]) {
loc = edgeX[cand[bs].second];
} else {
loc = edgeY[cand[bs].second];
}
res.push_back(loc);
}
answer(res[0], res[1]);
}
