记录每一层可以移动到的区间....非常多的细节...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int n,m;
typedef pair<int,int> pII;
vector<pII> vi;
vector<pII> duan[2],temp;
int hy[320000],ny=0;
int MX=-1;
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
vi.push_back(make_pair(a,b));
if(a-1>=1) hy[ny++]=a-1;
hy[ny++]=a;
if(a+1<=n) hy[ny++]=a+1;
}
hy[ny++]=n; hy[ny++]=1;
sort(hy,hy+ny);
ny=unique(hy,hy+ny)-hy;
sort(vi.begin(),vi.end());
int p=0;
int pre=0,now=1;
int left=-1;
if(vi[p].first==1)
{
for(;p<vi.size();p++)
{
if(vi[p].first==1)
{
if(left==-1) left=vi[p].second-1;
else left=min(left,vi[p].second-1);
}
else
{
p--; break;
}
}
if(left<1)
{
puts("-1");
return 0;
}
else duan[0].push_back(make_pair(1,left));
}
else duan[0].push_back(make_pair(1,n));
p=0;
for(int yy=0;yy<ny;yy++)
{
temp.clear();
int one=1,two;
while(vi[p].first==hy[yy])
{
two=vi[p].second-1;
if(two>=one)
{
temp.push_back(make_pair(one,two));
}
one=two+2;
p++;
}
if(one<=n) temp.push_back(make_pair(one,n));
duan[now].clear();
int id=0;
for(int i=0,sz=duan[pre].size(),ts=temp.size();i<sz&&id<ts;i++)
{
int from=duan[pre][i].first;
int to=duan[pre][i].second;
if(to<temp[id].first) continue;
while(id+1<ts&&temp[id].second<from)
id++;
if(to>=temp[id].first&&from<=temp[id].second)
{
duan[now].push_back( make_pair( max(from,temp[id].first)
, temp[id].second) );
if(hy[yy]==n)
{
MX=max(MX,temp[id].second);
}
id++; i--;
}
}
swap(now,pre);
}
if(MX>=n) printf("%d\n",2*n-2);
else printf("-1\n");
return 0;
}