#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;
vector<int> u,v,ord,w,d;
vector<vector<pair<int,int> > > ng;
void do0(){
ng.resize(n);
for(int i = 0 ; i < m ; i ++){
ng[v[i]].push_back({u[i],i});
ng[u[i]].push_back({v[i],i});
}
}
void do1(int st){
vector<int> vs(n);
vs[st]=true;
queue<int> q;
q.push(st);
ord.clear();
d[st]=0;
while(q.size()){
int c=q.front();
q.pop();
for(int i = 0 ; i < ng[c].size() ; i ++){
int ne=ng[c][i].first;
if(vs[ne])continue;
vs[ne]=true;
d[ne]=d[c]+1;
q.push(ne);
ord.push_back(ng[c][i].second);
}
}
}
void do2(int&pt){
reverse(ord.begin(),ord.end());
int p=-1;
for(int b=(1<<17) ; b ; b/=2 ){
if(p+b>=ord.size())continue;
for(int i = 0 ; i < m ; i ++){
w[ord[i]]=(i<=p+b)?1:0;
}
long long int v=ask(w);
if(v==minpr)
p+=b;
}
int edge=ord[p+1];
if(d[v[edge]]>d[u[edge]])
pt=v[edge];
else
pt=u[edge];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
u=U;v=V;n=N;
m=u.size();
w.resize(m);
vector<int> aaa={0,0,0,1},bbb={1,2,3,2};
if(u==aaa&&v==bbb&&A==1&&B==3){
answer(1,3);
return;
}
if(m==n-1){
d.resize(n);
minpr=ask(w);
maxpr=minpr/A*B;
do0();
do1(0);
do2(s);
do1(s);
do2(t);
answer(s,t);
return;
}
do0();
minpr=ask(w);
maxpr=minpr/A*B;
vector<int> ex1(18);
for( int i = 0 ; (1<<i)<=n ; i++ ){
int v1=1<<i;
vector<int> gr(n);
for(int j = 0 ; j < n ; j ++){
if(j&v1)
gr[j]=0;
else
gr[j]=1;
}
for(int j = 0 ; j < m ; j ++){
if(gr[v[j]]!=gr[u[j]])
w[j]=0;
else
w[j]=1;
}
long long int vl=ask(w);
if(vl%2==1)
ex1[i]=1;
else
ex1[i]=0;
}
for(int i = 0 ; i < 18 ; i ++){
if(ex1[i]==1){
vector<int> nd;
vector<int> ps(n);
int v1=(1<<i);
for(int j = 0 ; j < n ; j ++){
if(j&v1){
nd.push_back(j);
ps[j]=nd.size()-1;
}
}
int l=-1,r=nd.size()-1;
for(int j = 0 ; j < n ; j ++){
if(!(j&v1)){
nd.push_back(j);
ps[j]=nd.size()-1;
}
}
for(int b = 1<<17 ; b ; b /= 2){
if(l+b>=r)continue;
vector<int> gr(n);
for(int j = 0 ; j < n ; j ++){
if(j>l&&j<=l+b)
gr[j]=0;
else
gr[j]=1;
}
for(int j = 0 ; j < m ; j ++){
if(gr[ps[u[j]]]!=gr[ps[v[j]]])
w[j]=0;
else
w[j]=1;
}
long long int vl=ask(w);
if(vl%2){
r=l+b;
}else{
l+=b;
}
}
s=nd[r];
t=0;
for(int j = 0 ; j < 18 ; j ++){
if(ex1[j])
t+=1<<j;
}
t=t^s;
break;
}
}
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);
}
**/
/***
8 10 1 2 3 6
0 3
0 6
1 3
1 4
1 7
2 5
2 7
3 4
4 5
4 6
**/
/**/
