#include<bits/stdc++.h>
using namespace std;
int n,m,d[200010],f[200010];
vector<int> a[200010],v[200010];
double dp[200010];
bool cmp(int x,int y){
	return dp[x]<dp[y];
}
void solve(int x){
	if(x==n) return;
	sort(a[x].begin(),a[x].end(),cmp);
	double z=0,k=1e9,p=1;
	for(int i=0;i<a[x].size();i++){
		int y=a[x][i];
		z+=0.75*p*(dp[y]+i+1);
		p*=0.25;
		k=min(k,z+(dp[a[x][0]]+i+3)*p);
	}
	dp[x]=k;
}
int main(){
	memset(d,63,sizeof(d));
	priority_queue<pair<int,int> > q;
	int x,y;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	d[n]=0;
	q.push(make_pair(0,n));
	while(!q.empty()){
		int x=q.top().second; q.pop();
		if(f[x]) continue;
		f[x]=1;
		solve(x);
		for(int i=0;i<v[x].size();i++){
			int y=v[x][i];
			a[y].push_back(x);
			if(d[y]>d[x]+1){
				d[y]=d[x]+1;
				q.push(make_pair(-d[y],y));
			}
		}
	}
	printf("%.9lf",dp[1]);
	return 0;
}