https://www.luogu.com.cn/record/192984397

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace IO{
	char ibuf[(1<<20)+1],*iS,*iT;
#if ONLINE_JUDGE
#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
#else
#define gh() getchar()
#endif
	inline long long read(){
		char ch=gh();
		long long x=0;
		bool t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	const void File(bool b1,bool b2){
		if(b1)freopen("out.out","w",stdout);
		if(b2)freopen("2.in","r",stdin);
	}
	
}
using namespace IO;
int n,m,g[1145][3],t1,t2,t3,t4,t5;
double dis[1145],t6;
bool b[1145];
struct graph
{
	int x;
	double y;//x:id y:dis
}te1;
bool operator <(graph qwe,graph wer)
{
	return qwe.y<wer.y;
}
inline double d(int qwe,int wer)
{
	return sqrt((g[qwe][1]-g[wer][1])*(g[qwe][1]-g[wer][1])+
		(g[qwe][2]-g[wer][2])*(g[qwe][2]-g[wer][2]));
}
struct xy
{
	int from,to;
	double ds;
}te;
vector<xy> v[1145];
priority_queue<graph> q;
signed main()
{
	fill(dis,dis+1000,114514);
	n=read();m=read();// 0 to n
	for(int i=1;i<=m;++i)
	{
		g[i][1]=read();
		g[i][2]=read();
	}
	t1=t2=1;//t1:min t2:max
	for(int i=2;i<=m;++i)
	{
		if(g[i][1]<g[t1][1])t1=i;
		if(g[i][1]>g[t2][1])t2=i;
	}
	t3=m;
//	cerr<<t1<<" "<<g[t1][1]<<" "<<t2<<" "<<g[t2][1]<<endl;
	for(int i=1;i<=t3;++i)
	{
		if(g[i][1]==g[t1][1]&&g[t1][1]>0)
		{
			g[++m][1]=0;
			g[m][2]=g[i][2];
			t1=m;
		}
		if(g[i][1]==g[t2][1]&&g[t2][1]<n)
		{
			g[++m][1]=n;
			g[m][2]=g[i][2];
			t2=m;
		}
	}
	for(int i=1;i<=t3;++i)
	{
		for(int j=1;j<=t3;++j)
		{
			if(i==j)continue;
			te.from=i;
			te.to=j;
			te.ds=d(i,j)/2.0;
			v[i].push_back(te);
		}
	}
	for(int i=t3+1;i<=m;++i)
	{
		for(int j=1;j<=t3;++j)
		{
			te.from=i;
			te.to=j;
			te.ds=d(i,j);
			v[i].push_back(te);
			te.from=j;
			te.to=i;
			v[j].push_back(te);
		}
	}
	//from t1 to t2
	/*
	for(int i=1;i<=m;++i)
	{
		for(auto j:v[i])
		{
			cerr<<j.from<<" "<<j.to<<" "<<j.ds<<endl;
		}
	}*/
	te1.x=t1;
	te1.y=0;
	q.push(te1);
	dis[t1]=0;
	b[t1]=1;
	while(!q.empty())
	{
		te1=q.top();
		q.pop();
		//if(b[te1.x])continue;
		//b[te1.x]=1;
		t6=te1.y;
		for(auto i:v[te1.x])
		{
			te1.x=i.to;
			te1.y=max(t6,i.ds);
			if(te1.y<dis[i.to])
			{
				q.push(te1);
				dis[i.to]=te1.y;
			}
		}
	}
	printf("%.2lf",dis[t2]);
	return 0;
}