#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 100100*1;
const ll MOD = 998244353;
const ll INF = 1e16;
vector<pi> adj[MAXN];
bool chk[MAXN];
queue<pi> q;
vector<ll> d;
vector<int> v1, v2;
void bfs(int s, int t) {
d[s] = d[t] = 0; q.push(pi(s, 1)); q.push(pi(t, 2));
while(q.size()) {
int here = q.front().ff; int col = q.front().ss; q.pop();
if(col == 1) v1.push_back(here);
else v2.push_back(here);
for(auto [there,w] : adj[here]) {
if(d[there] > d[here]+1) {
d[there] = d[here]+1;
q.push(pi(there, col));
}
}
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int m = U.size();
for(int i=0; i<m; i++) {
adj[U[i]].push_back(pi(V[i], i));
adj[V[i]].push_back(pi(U[i], i));
}
vector<int> w(m);
ll len = ask(w)/A;
int lb = 0, ub = m-1, mid;
while(lb < ub) {
mid = lb+ub>>1;
w.clear(); w.resize(m);
for(int i=0; i<=mid; i++) w[i]=1;
ll res = ask(w);
if(res > A*len) {
ub = mid;
} else {
lb = mid+1;
}
} int e = lb;
int x = U[e], y = V[e];
d.resize(N, INF);
bfs(x, y);
lb = 0, ub = (int)v1.size()-1, mid;
while(lb < ub) {
mid = lb+ub>>1;
memset(chk, 0, sizeof chk);
for(int i=0; i<=mid; i++) chk[v1[i]]=1;
w.clear(); w.resize(m);
for(int i=0; i<m; i++) {
if(chk[U[i]]!=chk[V[i]]) w[i]=1;
} ll res = ask(w);
if(res == A*len) ub = mid;
else lb = mid+1;
} int p = v1[lb];
lb = 0, ub = (int)v2.size()-1, mid;
while(lb < ub) {
mid = lb+ub>>1;
memset(chk, 0, sizeof chk);
for(int i=0; i<=mid; i++) chk[v2[i]]=1;
w.clear(); w.resize(m);
for(int i=0; i<m; i++) {
if(chk[U[i]]!=chk[V[i]]) w[i]=1;
} ll res = ask(w);
if(res == A*len) ub = mid;
else lb = mid+1;
} int q = v2[lb];
answer(p, q);
}
