#include "highway.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 90005, M = 1300005;
const ll inf = 1e18;
int n, m, a, b, p;
ll def, dis[N];
bool ban[N], v1[N], v2[N];
vector<int> adj[N], dij[N], drv[N], ord;
vector<pii> edg;
queue<int> q;
ll query () {
vector<int> V;
for(int i=0;i<m;i++) {
V.push_back(ban[edg[i].X] || ban[edg[i].Y]);
}
return ask(V);
}
int getpiv () {
int S = 0, E = (int)ord.size() - 1;
while(S<E) {
int Z = (S+E)/2;
for(int i=0;i<=Z;i++) {
ban[ord[i]] = true;
}
query() != def ? E = Z : S = Z+1;
for(int i=0;i<=Z;i++) {
ban[ord[i]] = false;
}
}
return ord[S];
}
void dfs1 (int C) {
if(C == p || v1[C]) return;
v1[C] = true;
for(auto &T : drv[C]) {
dfs1(T);
}
}
void dfs2 (int C) {
if(v2[C]) return;
v2[C] = true;
for(auto &T : dij[C]) {
dfs2(T);
}
}
void find_pair(int _N, vector<int> _U, vector<int> _V, int _A, int _B) {
n = _N;
m = (int)_U.size();
a = _A;
b = _B;
for(int i=0;i<m;i++) {
edg.push_back({_U[i]+1, _V[i]+1});
adj[_U[i]+1].push_back(_V[i]+1);
adj[_V[i]+1].push_back(_U[i]+1);
}
def = query();
for(int i=1;i<=n;i++) {
ord.push_back(i);
}
p = getpiv();
ord.clear();
for(int i=1;i<p;i++) {
ban[i] = true;
}
for(int i=1;i<=n;i++) {
dis[i] = inf;
}
dis[p] = 0;
q.push(p);
while(!q.empty()) {
int C = q.front();
q.pop();
ord.push_back(C);
for(auto &T : adj[C]) {
if(T < p) continue;
if(dis[T] == inf) {
dis[T] = dis[C] + 1;
q.push(T);
}
if(dis[T] == dis[C] - 1) {
dij[T].push_back(C);
drv[C].push_back(T);
}
}
}
reverse(ord.begin(), ord.end());
int PA = getpiv();
ord.clear();
dfs1(PA);
for(int i=p;i<=n;i++) {
if(v1[i]) dfs2(i);
}
for(int i=p;i<=n;i++) {
if(!v2[i] && dis[i] + dis[PA] == def / a) ord.push_back(i);
}
int PB = getpiv();
ord.clear();
answer(PA-1, PB-1);
}
