#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 dfs(int t, int x, int d, int p) {
dist[t][x] = d;
for (int y : graph[x]) {
if (y == p) continue;
dfs(t, y, d+1, x);
}
}
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++) if (i != magicEdge) {
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;
dfs(0, edgeX[magicEdge], 0, -1);
dfs(1, edgeY[magicEdge], 0, -1);
vi edgesOnSideX;
for (int i = 0; i < nbE; i++) if (i != magicEdge) {
if (dist[0][edgeX[i]] == -1 || dist[0][edgeY[i]] == -1) continue;
assert(dist[0][edgeX[i]] != -1 && dist[0][edgeY[i]] != -1);
edgesOnSideX.push_back(i);
}
int increasedSideXDist = caller(edgesOnSideX);
assert((increasedSideXDist-distVert)%(bK-aK) == 0);
int distX = (increasedSideXDist-distVert)/(bK-aK);
int distY = (distVert/aK)-1-distX;
assert(0 <= distY);
for (int i = 0; i < n; i++) bounceOn[i] = -1;
for (int i = 0; i < nbE; i++) if (i != magicEdge) {
if (dist[0][edgeX[i]] == -1 || dist[0][edgeY[i]] == -1) continue;
assert(dist[0][edgeX[i]] != -1 && dist[0][edgeY[i]] != -1);
if (dist[0][edgeX[i]] > dist[0][edgeY[i]]) {
bounceOn[edgeX[i]] = i;
} else {
assert(dist[0][edgeX[i]] < dist[0][edgeY[i]]);
bounceOn[edgeY[i]] = i;
}
}
for (int i = 0; i < nbE; i++) if (i != magicEdge) {
if (dist[1][edgeX[i]] == -1 || dist[1][edgeY[i]] == -1) continue;
assert(dist[1][edgeX[i]] != -1 && dist[1][edgeY[i]] != -1);
if (dist[1][edgeX[i]] > dist[1][edgeY[i]]) {
bounceOn[edgeX[i]] = i;
} else {
assert(dist[1][edgeX[i]] < dist[1][edgeY[i]]);
bounceOn[edgeY[i]] = i;
}
}
for (int i = 0; i < n; i++) {
if (i == edgeX[magicEdge]) continue;
if (i == edgeY[magicEdge]) continue;
assert(bounceOn[i] != -1);
}
int ansX = edgeX[magicEdge];
if (distX > 0) {
vi possX;
for (int i = 0; i < n; i++) if (dist[0][i] == distX) {
assert(bounceOn[i] != -1);
assert(bounceOn[i] != magicEdge);
possX.push_back(bounceOn[i]);
}
assert(!possX.empty());
int loc = whoIncrease(possX, distVert);
if (dist[0][edgeX[loc]] > dist[0][edgeY[loc]]) {
ansX = edgeX[loc];
} else {
ansX = edgeY[loc];
}
}
int ansY = edgeY[magicEdge];
if (distY > 0) {
vi possY;
for (int i = 0; i < n; i++) if (dist[1][i] == distY) {
assert(bounceOn[i] != -1);
assert(bounceOn[i] != magicEdge);
possY.push_back(bounceOn[i]);
}
assert(!possY.empty());
int loc = whoIncrease(possY, distVert);
if (dist[1][edgeX[loc]] > dist[1][edgeY[loc]]) {
ansY = edgeX[loc];
} else {
ansY = edgeY[loc];
}
}
cout << ansX << " " << ansY << endl;
answer(ansX, ansY);
}
