#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;
vi graph [siz];
int dist [2][siz];
int bounceOn [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 (int y : graph[x]) {
if (dist[t][y] == -1) {
dist[t][y] = dist[t][x] + 1;
q.push(y);
}
}
}
}
int whoIncrease(vi edgeSet, int refD) {
while (sz(edgeSet) != 1) {
assert(!edgeSet.empty());
vi leftSet, rightSet;
for (int i : edgeSet) {
if (sz(leftSet) <= sz(rightSet)) {
leftSet.push_back(i);
} else {
rightSet.push_back(i);
}
}
int loc = caller(leftSet);
assert(loc >= refD);
if (loc > refD) {
edgeSet = leftSet;
}
else {
edgeSet = rightSet;
}
}
return edgeSet[0];
}
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]);
graph[edgeY[i]].push_back(edgeX[i]);
}
for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++) dist[i][j] = -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;
}
}
for (int i = 0; i < n; i++) bounceOn[i] = -1;
for (int t = 0; t < 2; t++) {
for (int i = 0; i < nbE; i++) if (i != magicEdge) {
if (dist[t][edgeX[i]] == -1 || dist[t][edgeY[i]] == -1) continue;
if (dist[t][edgeX[i]] > dist[t][edgeY[i]]) {
bounceOn[edgeX[i]] = i;
} else {
bounceOn[edgeY[i]] = i;
}
}
}
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) {
if (bounceOn[i] != -1) {
cand.push_back({min(dist[t][edgeX[bounceOn[i]]], dist[t][edgeY[bounceOn[i]]]), bounceOn[i]});
}
}
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);
}
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]);
}
