#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
/*
int N,M,A,B,S,T;
vector<int> U,V;
vector<vector<pair<int,int> > > NG;
long long int ask(vector<int> W){
queue<pair<long long int,int> > q;
q.push({0,S});
vector<long long int> dst(N,1e16);
dst[S]=0;
while(q.size()){
pair<int,int> cur=q.front();
long long int d=-cur.first;
long long int nd=cur.second;
q.pop();
for(int i = 0 ; i < NG[nd].size() ; i ++){
int ne=NG[nd][i].first;
int ew=NG[nd][i].second;
ew=W[ew]*(B-A)+A;
if(d+ew<dst[ne]){
dst[ne]=d+ew;
q.push({-dst[ne],ne});
}
}
}
return dst[T];
}
void answer(int A,int B){
cout<<A<<" "<<B<<endl;
}*/
int n,m,a,b,s,t;
long long int minpr,maxpr,tmp;
vector<int> u,v,ord,w,d;
vector<vector<pair<long long int,int> > > ng;
vector<vector<int> > bfs(int st,int ed){
vector<vector<int> > rz(n,{n+1,0,0});
rz[st]={0,ed,st};
priority_queue<vector<int> > q;
q.push({rz[st]});
while(q.size()){
vector<int> cr=q.top();
q.pop();
int cn=cr[2];
int cd=-cr[0];
for(int i = 0 ; i < ng[cn].size() ; i ++ ){
int ne=ng[cn][i].first;
int en=ng[cn][i].second;
if(rz[ne][0]>cd+1){
rz[ne]={-cd-1,en,ne};
q.push(rz[ne]);
rz[ne][0]*=-1;
}
}
}
return rz;
}
int fnd(vector<vector<int> > s0){
w.clear();
w.resize(m,1);
for(int i = 0 ; i < s0.size() ; i ++){
w[s0[i][1]]=0;
}
long long int q=ask(w);
int l=0,r=s0.size();
while(l!=r-1){
int md=(l+r)/2;
w.clear();
w.resize(m,1);
for(int i = 0 ; i < md ; i ++)
w[s0[i][1]]=0;
tmp=ask(w);
if(tmp==q){
r=md;
}else{
l=md;
}
}
return s0[l][2];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
u=U;v=V;n=N;
m=u.size();
ng.resize(n);
for(int i = 0 ; i < m ; i ++){
ng[u[i]].push_back({v[i],i});
ng[v[i]].push_back({u[i],i});
}
w.resize(m);
minpr=ask(w);
maxpr=minpr/A*B;
int l=0,r=m;
while(l!=r-1){
int md=(l+r)/2;
for(int i = 0 ; i < m ; i ++){
if(i<md)
w[i]=1;
else
w[i]=0;
}
tmp=ask(w);
if(tmp==minpr){
l=md;
}else{
r=md;
}
}
vector<vector<int> > g1=bfs(u[l],l);
vector<vector<int> > g2=bfs(v[l],l);
vector<vector<int> > s1,s2;
for(int i = 0 ; i < n ; i ++){
if(g1[i][0]<g2[i][0]){
s1.push_back(g1[i]);
}else if(g2[i][0]<g1[i][0]){
s2.push_back(g2[i]);
}
}
sort(s1.begin(),s1.end());
sort(s2.begin(),s2.end());
t=fnd(s1);
s=fnd(s2);
answer(s,t);
}
/*
int main(){
cin>>N>>M>>A>>B>>S>>T;
U.resize(M);
V.resize(M);
NG.resize(N);
for(int i = 0 ; i < M ; i ++){
cin>>U[i]>>V[i];
NG[U[i]].push_back({V[i],i});
NG[V[i]].push_back({U[i],i});
}
find_pair(N,U,V,A,B);
}
*/
