#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// find_by_order(), order_of_key()
typedef long long ll;
typedef long double dd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<dd, dd> pdd;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<dd> vdd;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdd;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vdd> vvdd;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef vector<vpdd> vvpdd;
typedef vector<bool> vb;
const int inf = 1 << 30;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define ffor(i, a, b) for(ll i = a; i < b; i++)
#define forin(x, a) for (auto &x: a)
#define all(x) x.begin(), x.end()
#ifdef TEST
#define dbg(x) cout << #x << ": " << x << '\n';
#define dbgc(x) cout << #x << ":"; forin(a, x) { cout << " " << a; } cout << endl;
#define tassert(x) assert(x);
#else
#define dbg(x)
#define dbgc(x)
#define tassert(x)
#endif
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
bool t3 = true;
rep(i, M) {
if (U[i] != i || V[i] != i + 1) {
t3 = false;
break;
}
}
if (t3) {
ll dist = ask(vii(M, 0)) / A;
int lo = 0, hi = N - 1 - dist;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
vii query(M, 0);
rep(i, mid) {
query[i] = 1;
}
if (ask(query) > dist * A) {
hi = mid - 1;
} else {
lo = mid;
}
}
answer(lo, lo + dist);
} else if (M == N - 1) {
vvpii adj(N);
rep(i, M) {
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
vpii parent(N, {-1, -1});
parent[0] = {-2, -2};
vii depth(N, -1);
depth[0] = 0;
deque<int> q = {0};
while (!q.empty()) {
int u = q.front();
q.pop_front();
forin(p, adj[u]) {
if (parent[p.first].first == -1) {
parent[p.first] = {u, p.second};
depth[p.first] = depth[u] + 1;
q.emplace_back(p.first);
}
}
}
ll dist = ask(vii(M, 0)) / A;
vii candidates;
rep(i, N) {
if (depth[i] == dist) {
candidates.emplace_back(i);
}
}
while (candidates.size() > 1) {
vii a, b, query(M);
rep(i, candidates.size()) {
if (i & 1) {
a.emplace_back(candidates[i]);
query[parent[candidates[i]].second] = 1;
} else {
b.emplace_back(candidates[i]);
}
}
if (ask(query) > dist * A) {
candidates = move(a);
} else {
candidates = move(b);
}
}
answer(0, candidates[0]);
}
}
