感谢@AC_vitasoy 的提醒。。看了看有个比较严重的错误漏洞。。好吧。。这数据这么弱好无奈(其实是自己写的搓)。


题意很简单。这题是真的可以做出来的。但是用set TLE了。。赛后才做出来的。。就差这么一题。。
其实早就想到这种做法。但是懒得写。。以为不会过。。没想到真不科学。。强行打脸。

//author: CHC
//First Edit Time: 2015-06-18 13:49
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+5+1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
int n,m,a,b;
/*
struct Edge {
int to,next;
Edge(){}
Edge(int _to,int _next):to(_to),next(_next){}
}e[MAXM];
int head[MAXN],tot;
inline void init(){
memset(head,-1,sizeof(head));
tot=0;
ss.clear();
}
inline void AddEdge(int u,int v){
e[tot]=Edge(v,head[u]);
head[u]=tot++;
e[tot]=Edge(u,head[v]);
head[v]=tot++;
ss.insert(pp(u,v));
ss.insert(pp(v,u));
}
*/
vector <int> e[MAXN];
inline void init(){
for(int i=0;i<=n;i++)e[i].clear();
}
inline void AddEdge(int u,int v){
e[u].push_back(v);
e[v].push_back(u);
}
int dis[MAXN];
int que[MAXN+1000],front,rear;
inline int bfsa(){
for(int i=1;i<=n;i++)dis[i]=-1;
dis[1]=0;
front=rear=0;
que[front++]=1;
while(front!=rear){
int now=que[rear++];
if(now==n)break;
int sz=e[now].size();
for(int i=0;i<sz;i++){
int to=e[now][i];
if(dis[to]==-1){
dis[to]=dis[now]+1;
if(now==n)break;
que[front++]=to;
}
}
}
return dis[n];
}
inline int bfsb(){
for(int i=1;i<=n;i++)dis[i]=-1;
dis[1]=0;
front=rear=0;
que[front++]=1;
que[front++]=n;
dis[n]=(0<<1)|1;
while(front!=rear){
int now=que[rear++];
for(int i=2;i<=n;i++){
int pos=lower_bound(e[now].begin(),e[now].end(),i)-e[now].begin();
int sz=e[now].size();
if(pos==sz||sz==0||(pos<sz&&e[now][pos]!=i)){
if(dis[i]==-1){
//if(pos<sz&&e[now][pos]!=i){
//printf("%d-->%d\n",now,i);
dis[i]=(((dis[now]>>1)+1)<<1)|(dis[now]&1);
que[front++]=i;
//}
/*
it=ss.find(pp(now,i));
if(it==ss.end()){
dis[i]=(((dis[now]>>1)+1)<<1)|(dis[now]&1);
que[front++]=i;
}
*/
}
else if((dis[i]&1)^(dis[now]&1)){
return (dis[i]>>1)+(dis[now]>>1)+1;
}
}
}
}
return -1;
}
int main()
{
while(~scanf("%d%d%d%d",&n,&m,&a,&b)){
init();
int flag=0;
for(int i=0,x,y;i<m;i++){
scanf("%d%d",&x,&y);
if(x==1&&y==n)flag=1;
if(x==n&&y==1)flag=1;
AddEdge(x,y);
}
for(int i=1;i<=n;i++)
sort(e[i].begin(),e[i].end());
LL atime,btime;
atime=(LL)bfsa()*a;
btime=(LL)bfsb()*b;
LL ans;
if(atime<0)ans=btime;
else if(btime<0)ans=atime;
else ans=min(atime,btime);
printf("%lld\n",ans);
/*
if(flag){
btime=(LL)bfsb()*b;
//printf("%I64d\n",btime);
if(btime<0)printf("%d\n",a);
else if(btime<a)printf("%lld\n",btime);
else printf("%d\n",a);
}
else {
atime=(LL)bfsa()*a;
//printf("bfsa:%I64d\n",atime);
if(atime<0)printf("%d\n",b);
else if(atime<b)printf("%lld\n",atime);
else printf("%d\n",b);
}
*/
}
return 0;
}