#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "highway.h"
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 90010;
vector<pii> adj[MAXN]; // index, eid
int dep[MAXN];
int eid[MAXN];
int typ[MAXN];
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
cerr << A << " " << B << "\n";
int M = U.size();
LL dist = ask(vector<int>(M, 0));
assert(dist % A == 0);
auto out = [&](int x) { cout << "(" << U[x] << ", " << V[x] << ")\n" << flush; };
For(i, 0, M - 1) {
adj[U[i]].eb(V[i], i);
adj[V[i]].eb(U[i], i);
}
int hi = M - 1, lo = -1;
while(hi - lo > 1) {
int mi = lo + (hi - lo) / 2;
vector<int> w(M, 0);
fill(w.begin(), w.begin() + mi + 1, 1);
LL d2 = ask(w);
if(d2 > dist) hi = mi;
else lo = mi;
}
int a = U[hi], b = V[hi];
cout << "key edge: " << hi << " "; out(hi);
// build bfs tree
memset(typ, -1, sizeof(typ));
queue<int> que;
dep[a] = 1; dep[b] = 1;
eid[a] = eid[b] = hi;
typ[a] = 0; typ[b] = 1;
que.emplace(a); que.emplace(b);
vector<int> ed[2];
vector<int> w0(M, 1);
while(!que.empty()) {
int cur = que.front(); que.pop();
w0[eid[cur]] = 0;
ed[typ[cur]].eb(eid[cur]);
for(auto &e:adj[cur]) if(typ[e.F] == -1 && e.S >= hi) {
dep[e.F] = dep[cur] + 1;
eid[e.F] = e.S;
typ[e.F] = typ[cur];
que.emplace(e.F);
}
}
// cout << "bfs tree #0\n"; for(auto &id:ed[0]) out(id);
// cout << "bfs tree #1\n"; for(auto &id:ed[1]) out(id);
int m = sz(ed[0]);
hi = m; lo = -1;
while(hi - lo > 1) {
int mi = lo + (hi - lo) / 2;
vector<int> w(all(w0));
For(i, mi, m - 1) w[ed[0][i]] = 1;
auto d2 = ask(w);
if(d2 == dist) hi = mi;
else lo = mi;
}
dep[b] = 0;
int id = ed[0][lo];
int x0 = U[id];
if(dep[V[id]] > dep[U[id]]) x0 = V[id];
cout << "x0: " << x0 << "\n";
dep[b] = 1;
m = sz(ed[1]);
hi = m; lo = -1;
while(hi - lo > 1) {
int mi = lo + (hi - lo) / 2;
vector<int> w(all(w0));
For(i, mi, m - 1) w[ed[1][i]] = 1;
auto d2 = ask(w);
if(d2 == dist) hi = mi;
else lo = mi;
}
dep[a] = 0;
id = ed[1][lo];
int x1 = U[id];
if(dep[V[id]] > dep[U[id]]) x1 = V[id];
cout << "x1: " << x1 << "\n";
dep[a] = 1;
answer(x0, x1);
// for (int j = 0; j < 50; ++j) {
// std::vector<int> w(M);
// for (int i = 0; i < M; ++i) {
// w[i] = 0;
// }
// long long toll = ask(w);
// }
// answer(0, N - 1);
}
/*
4 4 1 3 1 3
0 1
0 2
0 3
1 2
*/
