#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int N = 1e6;
vector<pii> g[N];
int n, m1;
void find_pair(int n1, vector<int> u, vector<int> v, int a, int b) {
n = n1, m1 = sz(u);
for (int i = 0; i < m1; i++) {
g[u[i]].push_back({v[i], i});
g[v[i]].push_back({u[i], i});
}
vector<int> w(sz(u));
ll dt = ask(w);
int l = 0, r = sz(u) - 1;
while (l <= r) {
int m = (l + r) / 2;
for (int i = 0; i <= m; i++) w[i] = 1;
if (ask(w) == dt) l = m + 1;
else r = m - 1;
for (int i = 0; i <= m; i++) w[i] = 0;
}
int x = u[l], y = v[l];
queue<int> q;
vector<int> d(n, -1), tp(n, -1), is(m1);
vector<pii> s[2][n];
d[x] = 0, d[y] = 0;
tp[x] = 0, tp[y] = 1;
is[l] = -1;
s[0][0] = {{x, l}};
s[1][0] = {{y, l}};
q.push(x);
q.push(y);
while (sz(q)) {
int a = q.front();
q.pop();
for (auto [to, id]: g[a]) {
if (d[to] == -1) {
tp[to] = tp[a];
d[to] = d[a] + 1;
q.push(to);
s[tp[to]][d[to]].push_back({to, id});
is[id] = 1;
}
}
}
for (int i = 0; i < m1; i++) {
if (!is[i]) {
w[i] = 1;
continue;
}
}
for (int i = 0; i < m1; i++) {
if (is[i] == 1 && tp[u[i]]) w[i] = 1;
}
ll td = ask(w);
int dt1 = (td - dt) / (b - a);
for (int i = 0; i < m1; i++) {
if (is[i] == 1 && tp[u[i]]) w[i] = 0;
}
int dt0 = dt / a - dt1 - 1;
l = 0, r = sz(s[0][dt0]) - 1;
while (l <= r) {
int m = (l + r) / 2;
for (int i = 0; i <= m; i++) {
w[s[0][dt0][i].s] = 1;
}
if (ask(w) == dt) l = m + 1;
else r = m - 1;
for (int i = 0; i <= m; i++) {
w[s[0][dt0][i].s] = 0;
}
}
int ans0 = s[0][dt0][l].f;
l = 0, r = sz(s[1][dt1]) - 1;
while (l <= r) {
int m = (l + r) / 2;
for (int i = 0; i <= m; i++) {
w[s[1][dt1][i].s] = 1;
}
if (ask(w) == dt) l = m + 1;
else r = m - 1;
for (int i = 0; i <= m; i++) {
w[s[1][dt1][i].s] = 0;
}
}
int ans1 = s[1][dt1][l].f;
answer(ans0, ans1);
}
