#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
#include "highway.h"
#define int ll
const int nmax = 1e5 + 5;
vector<pii> g[nmax];
int N, M;
int Ask(vector<int> a) {
vector<signed> b;
for(auto x : a) b.emplace_back(x);
return ask(b);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void find_pair(signed n__, std::vector<signed> U, std::vector<signed> V, signed A_cost, signed B_cost) {
N = n__;
M = sz(U);
for(int i = 0; i < sz(U); i++)
g[U[i]].emplace_back(V[i], i),
g[V[i]].emplace_back(U[i], i);
int standard_ = Ask(vector<int>(M, 0));
int lenght = standard_ / A_cost;
int root = -1, r = N;
while(root + 1 < r) {
int cand = (root + r) / 2;
if(cand >= N) continue;
vector<int> A(M, 0);
for(int i = 0; i <= cand; i++)
for(auto [x, e] : g[i])
A[e] = 1;
if(Ask(A) == standard_)
root = cand;
else
r = cand;
}
root++;
//cerr << root << '\n';
vector<int> list, p(N, -1);
vector<int> arriv(N, 0);
vector<vector<int>> bydist(N, vector<int>());
queue<int> que;
que.emplace(root);
p[root] = root;
while(!que.empty()) {
int node = que.front();
que.pop();
if(node < root) {
p[node] = -1;
continue;
}
bydist[arriv[node]].emplace_back(node);
list.emplace_back(node);
shuffle(all(g[node]), rng);
for(auto [x, e] : g[node]) {
if(p[x] == -1)
p[x] = node, que.emplace(x),
arriv[x] = arriv[node] + 1;
}
}
int S = sz(list), l = 0;
while(l + 1 < S) {
int cand = (S + l) / 2;
if(cand < 0) continue;
vector<int> A(M, 0);
for(int i = 0; i < root; i++)
for(auto [x, e] : g[i])
A[e] = 1;
for(int a = cand; a < sz(list); a++)
for(auto [x, e] : g[list[a]])
A[e] = 1;
if(Ask(A) == standard_) S = cand;
else l = cand;
}
S--;
S = list[S];
//cerr << S << '\n';
vector<int> exonerate(N, 0);
int tmp = S;
while(tmp != root) exonerate[tmp] = 1, tmp = p[tmp];
//cerr << '\n';
list = move(bydist[lenght - arriv[S]]);
int T = sz(list); l = 0;
while(l + 1 < T) {
int cand = (T + l) / 2;
if(cand < 0) continue;
vector<int> A(M, 0);
for(int i = 0; i < root; i++)
for(auto [x, e] : g[i])
A[e] = 1;
for(int a = cand; a < sz(list); a++)
if(!exonerate[list[a]])
for(auto [x, e] : g[list[a]])
A[e] = 1;
if(Ask(A) == standard_) T = cand;
else l = cand;
}
T = list[T - 1];
answer(S, T);
return;
}
#undef int
