// M
#include<bits/stdc++.h>
#include "highway.h"
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 90004, TOF = N / 3;
int n, m, ca, cb, dist, root, H[N];
ll MnCost;
vector < int > alwaysMarked;
vector < pair < int , int > > Adj[N];
inline ll Ask(vector < int > vec)
{
vector < int > TMp(m, 0);
for (int i : vec)
TMp[i] = 1;
return ask(TMp);
}
inline bool HasImpact(vector < int > vec)
{
return (Ask(vec) > MnCost);
}
inline vector < int > MarkAll(vector < int > vec)
{
vector < int > TMp(m, 0), ret;
for (int i : vec)
for (auto e : Adj[i])
TMp[e.second] = 1;
for (int i : alwaysMarked)
for (auto e : Adj[i])
TMp[e.second] = 1;
for (int i = 0; i < m; i ++)
if (TMp[i])
ret.pb(i);
return ret;
}
void find_pair(int _n, vector < int > _U, vector < int > _V, int _A, int _B)
{
n = _n;
m = (int)_U.size();
for (int i = 0; i < m; i ++)
{
Adj[_U[i]].pb({_V[i], i});
Adj[_V[i]].pb({_U[i], i});
}
ca = _A; cb = _B;
MnCost = Ask(vector < int > {});
dist = MnCost / ca;
auto GenerateVec = [](int l, int r){
vector < int > vec;
for (int i = l; i < r; i ++)
vec.pb(i);
return vec;
};
int le = 0, ri = n, md;
if (n > TOF * 2 && HasImpact(MarkAll(GenerateVec(0, TOF))))
le = 0, ri = TOF;
else if (n > TOF * 2)
alwaysMarked = GenerateVec(0, TOF), le = TOF, ri = n;
while (ri - le > 1)
{
md = (le + ri) >> 1;
if (HasImpact(MarkAll(GenerateVec(0, md))))
ri = md;
else
le = md;
}
alwaysMarked = GenerateVec(0, le);
root = le;
queue < int > qu;
memset(H, -1, sizeof(H));
H[root] = 0; qu.push(root);
while (qu.size())
{
int v = qu.front();
qu.pop();
for (auto u : Adj[v])
if (u.first >= le && H[u.first] == -1)
H[u.first] = H[v] + 1, qu.push(u.first);
}
vector < int > Rs;
vector < int > marked(n, 0);
for (int i : alwaysMarked)
marked[i] = 1;
for (int w = 0; w < 2; w ++)
{
vector < int > srt;
for (int i = 0; i < n; i ++)
if (marked[i] == 0)
srt.pb(i);
sort(srt.begin(), srt.end(), [&](int i, int j){return H[i] > H[j];});
auto GenVec = [&](int l, int r){
assert(r <= (int)srt.size());
vector < int > vec;
for (int i = l; i < r; i ++)
vec.pb(srt[i]);
return vec;
};
le = 0, ri = (int)srt.size();
if (srt.size() > TOF * 2 && HasImpact(MarkAll(GenVec(0, TOF))))
le = 0, ri = TOF;
else if (srt.size() > TOF * 2)
{
for (int i = 0; i < TOF; i ++)
alwaysMarked.pb(srt[i]);
le = TOF;
}
while (ri - le > 1)
{
md = (le + ri) >> 1;
if (HasImpact(MarkAll(GenVec(0, md))))
ri = md;
else
le = md;
}
Rs.pb(srt[le]);
qu.push(srt[le]);
marked[srt[le]] = 1;
while (qu.size())
{
int v = qu.front();
qu.pop();
alwaysMarked.pb(v);
for (auto u : Adj[v])
if (!marked[u.first] && u.first != root)
marked[u.first] = 1, qu.push(u.first);
}
}
assert((int)Rs.size() == 2);
answer(Rs[0], Rs[1]);
return ;
}
