#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int M;
ll nask (vector<int> v) {
vector<int> w(M, 0);
for (int i : v) w[i] = 1;
return ask (w);
}
ll rask (vector<int> v) {
vector<int> w(M, 1);
for (int i : v) w[i] = 0;
return ask (w);
}
const int MAXN = 2e5;
vector<pair<int,int>> g[MAXN], mb, h[2][MAXN];
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
M = U.size();
for (int i = 0 ; i < M ; ++ i) {
g[U[i]].push_back ({V[i], i});
g[V[i]].push_back ({U[i], i});
}
ll dist = nask ({}) / A;
int l = 0, r = M - 1;
while (l < r) {
int m = (l + r) >> 1;
vector<int> now;
for (int i = l ; i <= m ; ++ i) {
now.push_back (i);
}
if (rask (now) < dist * B) {
r = m;
} else {
l = m + 1;
}
}
int ei = r;
int u = U[r], v = V[r];
assert (rask({r}) < dist*B);
vector<int>from(N,-1);
vector<int>id(N,-1);
vector<int>d(N,MAXN);
queue<int>q;
q.push(u),q.push(v);
d[u] = d[v] = 0;
from[u] = 0;
from[v] = 1;
while(q.size()) {
int v = q.front(); q.pop();
for (auto [to, i] : g[v]) if (d[to] > d[v] + 1) {
from[to] = from[v];
d[to] = d[v] + 1;
q.push(to);
id[to] = i;
}
}
for (int i = 0 ; i < N ; ++ i) {
h[from[i]][d[i]].push_back ({i, id[i]});
}
vector<int>ans(2,-1);
// cout << u << " <-> " << v << "\n";
for (int i = 0 ; i < 2 ; ++ i) {
vector<pair<int,int>>now;
for(int F = 0 ; F <= N ; ++ F) {
for (auto p : h[i][F]) now.push_back (p);
}
// for(auto p : now)cout<<p.first<<" ";
// cout<<"\n";
assert (now.size());
int l = 0, r = now.size() - 1;
// int ans = 0;
while (l < r) {
int m = (l + r + 1) >> 1;
vector<int>cur={ei};
// cout<<l<<" "<<r<<" []\n";
for(int ia = m; ia <= r ; ++ ia) {
cur.push_back(now[ia].second);
}
if(rask(cur)==dist*B-B+A) {
// ans = m - 1;
r = m - 1;
} else {
l = m;
}
}
ans[i] = now[l].first;
}
// cout<<ans[0] << " " << ans[1] << " www\n";
answer (ans[0], ans[1]);
}
