#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "highway.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pll pair<long long, long long>
#define pii pair<int, int>
using namespace std;
//const int N = 2e5 + 10;
int n, m, max_height = 0, timer;
vector < vector <pii> > g, gr;
vector < vector <int> > fixed_h;
vector <int> h;
vector <pii> par;
void dfs(int u, int p, int id_w, int height) {
max_height = max(max_height, height);
h[u] = height;
par[u] = {p, id_w};
for (auto to : gr[u])
if (to.fi != p)
dfs(to.fi, u, to.se, h[u] + 1);
}
int get_answer(vector <int> candidates, vector <int> vertical, ll val) {
vector <int> L, R, w;
while (candidates.size() > 1) {
L.clear(); R.clear();
w.assign(m, 0);
for (int to : vertical)
w[to] = 1;
int lim = candidates.size() / 2;
for (int i = 0; i < lim; i++) {
int u = candidates[i];
L.pb(u);
if (par[u].se >= 0)
w[par[u].se] = 1;
}
for (int i = lim; i < candidates.size(); i++) {
R.pb(candidates[i]);
}
ll curval = ask(w);
if (curval > val)
candidates = L;
else
candidates = R;
}
return candidates[0];
}
int solve_from(int C, int dist, ll val, vector <int> vertical) {
max_height = 0; timer = 0;
dfs(C, -1, -1, 0);
fixed_h.resize(max_height + 1);
for (int i = 0; i < n; i++)
fixed_h[h[i]].pb(i);
return get_answer(fixed_h[dist], vertical, val);
}
void bfs_tree(int x) {
queue <int> q;
q.push(x);
vector <bool> vis(n, false);
vis[x] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto to : g[cur]) {
if (vis[to.fi])
continue;
vis[to.fi] = true;
q.push(to.fi);
// cout << cur << " " << to.fi << endl;
gr[cur].pb(to);
gr[to.fi].pb({cur, to.se});
}
}
}
bool cmp(pii x, pii y) {return x.se > y.se;}
void find_pair(int n1, vector <int> U, vector <int> V, int A, int B) {
n = n1;
m = U.size();
g.resize(n);
gr.resize(n);
for (int i = 0; i < m; i++) {
g[U[i]].pb({V[i], i});
g[V[i]].pb({U[i], i});
}
vector <int> w(m, 0);
ll val = ask(w);
int dist = (val / (A * 1ll));
int L = 0, R = n - 1, M, x = n;
while (L <= R) {
w.assign(m, 0);
M = (L + R) / 2;
for (int i = 0; i <= M; i++)
for (auto to : g[i])
w[to.se] = 1;
ll curval = ask(w);
if (curval > val) {
x = min(x, M);
R = M - 1;
} else
L = M + 1;
}
// cout << x << endl;
// return;
bfs_tree(x);
vector <bool> vis(m, false);
vector <int> vertical;
for (int i = 0; i < n; i++)
for (auto to : gr[i])
vis[to.se] = true;
for (int i = 0; i < m; i++)
if (!vis[i])
vertical.pb(i);
// return;
h.resize(n);
par.resize(n);
dfs(x, -1, -1, 0);
vector <pii> c(n);
for (int i = 0; i < n; i++)
c[i] = {i, h[i]};
sort(c.begin(), c.end(), cmp);
L = 0; R = n - 1;
int idc = n - 1;
while (L <= R) {
w.assign(m, 0);
for (int to : vertical)
w[to] = 1;
M = (L + R) / 2;
for (int i = 0; i <= M; i++)
if (par[c[i].fi].fi != -1)
w[par[c[i].fi].se] = 1;
ll curval = ask(w);
if (curval > val) {
idc = min(idc, M);
R = M - 1;
} else
L = M + 1;
}
int s = c[idc].fi;
// cout << s << endl;
int t = solve_from(s, dist, val, vertical);
// cout << t << endl;
answer(s, t);
}
