题解：
这一题感觉和noip2015d2t3一模一样，而且是弱化版
但是，后来发现貌似每两个点都可以建立虫洞
好在是i和i+1有边，所以就直接用二分+贪心了
代码：
#include<bits/stdc++.h>
const int N=,inf=<<;
using namespace std;
int n,m,l[N],r[N];
bool check(int mid)
{
int d1=-inf,d2=<<,c1=-inf,c2=<<;
for(int i=;i<=m;i++)
{
if(r[i]-l[i]<=mid) continue;
d1=max(d1,l[i]+r[i]-mid);
d2=min(d2,l[i]+r[i]+mid);
c1=max(l[i]-r[i]-mid,c1);
c2=min(l[i]-r[i]+mid,c2);
if(d1>d2||c1>c2) return ;
}
return ;
}
int read()
{
int x=;char c;
for (;c<''||c>'';c=getchar());
for (;c>=''&&c<='';c=getchar())x=x*+c-;
return x;
}
int main()
{
n=read();m=read();
for(int i=;i<=m;i++)
{
l[i]=read();r[i]=read();
if (l[i]>r[i])swap(l[i],r[i]);
}
int l=,r=n,ans=-;
while(l<r)
{
int mid=(l+r)/;
if(check(mid))r=mid;
else l=mid+;
}
printf("%d",l);
}