#include "highway.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
typedef long long ll;
const int MAXN = 90055;
const int MAXM = 130055;
vector<int> G[MAXN], BEV;
vector<int> PEV[2][MAXN], O[2];
int C[2][MAXN], D[2][MAXN];
int A[MAXM], B[MAXM];
int ud[MAXN];
int N, M, CA, CB, L, W, AS, AT;
int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }
void getW() {
int s = 0, e = M-1; for(int m; s < e;) {
m = (s+e) >> 1;
vector<int> V(M, 0);
fill(V.begin(), V.begin()+m+1, 1);
if(ll(L)*CA < ask(V)) e = m;
else s = m+1;
}
W = s;
}
void calC() {
for(int i = 0; i < M; i++) {
G[A[i]].eb(i);
G[B[i]].eb(i);
}
for(int t : {0, 1}) {
queue<int> PQ;
C[t][(t ? B : A)[W]] = 1;
PQ.push((t ? B : A)[W]);
for(int i, d; !PQ.empty(); PQ.pop()) {
i = PQ.front();
d = C[t][i] + 1;
for(int e : G[i]) {
int v = A[e] + B[e] - i;
if(C[t][v]) continue;
C[t][v] = d;
PQ.push(v);
}
}
}
}
void dfs(int D[], vector<int> PEV[], int i) {
for(int e : G[i]) {
int v = A[e] + B[e] - i;
PEV[v].eb(e);
if(D[v]) continue;
D[v] = D[i] + 1;
dfs(D, PEV, v);
}
}
void findS() {
int s = 0, e = sz(O[0])-1; for(int m; s < e;) {
m = (s+e) >> 1;
vector<int> V = BEV;
for(int i = 0; i <= m; i++)
V[PEV[0][O[0][i]][0]] = 1;
if(ll(L)*CA < ask(V)) e = m;
else s = m+1;
}
AS = O[0][s];
}
void findT() {
vector<int> HV;
int dep = L-D[0][AS]+1;
for(int i = 0; i < N; i++) if(dep == D[1][i]) HV.eb(i);
int s = 0, e = sz(HV)-1; for(int m; s < e;) {
m = (s+e) >> 1;
vector<int> V = BEV;
for(int i = 0; i <= m; i++)
V[PEV[1][HV[i]][0]] = 1;
if(ll(L)*CA < ask(V)) e = m;
else s = m+1;
}
AT = HV[s];
}
void solve() {
L = ask(vector<int>(M, 0)) / CA;
getW();
calC();
for(int i = 0; i < N; i++) G[i].clear();
for(int i = 0, a, b; i < M; i++) {
a = A[i]; b = B[i];
if(C[0][a] == C[0][b] || C[1][a] == C[1][b]
|| C[0][a] == C[1][a] || C[0][b] == C[1][b]
|| (C[0][a] < C[0][b]) != (C[1][a] < C[1][b])) {
BEV.eb(1);
continue;
}
BEV.eb(0);
if(C[0][a] < C[0][b]) G[a].eb(i);
else G[b].eb(i);
}
BEV[W] = 0;
for(int t : {0, 1}) {
int v = (t ? B : A)[W];
D[t][v] = 1; PEV[t][v].eb(W);
dfs(D[t], PEV[t], v);
for(int i = 0; i < N; i++)
if(D[t][i]) O[t].eb(i);
sort(allv(O[t]), [&](int a, int b) {
return D[t][a] > D[t][b];
});
iota(ud, ud+N, 0);
for(int v : O[t]) {
auto &V = PEV[t][v];
int pe = -1;
for(int e : V) {
int p = A[e] + B[e] - v;
if(uf(p) == uf(v)) continue;
uf(p, v);
pe = e;
break;
}
for(int e : V) if(e != pe) BEV[e] = 1;
V.clear(); V.eb(pe);
}
}
findS();
findT();
answer(AS, AT);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
::N = N; ::M = U.size(); ::CA = A; ::CB = B;
for(int i = 0; i < ::M; i++) {
::A[i] = U[i];
::B[i] = V[i];
}
solve();
}
