（已经有了简化版题面）
又秒了一次dp233
本来按照感觉瞎写了一发...
但还是老老实实列式子吧....
对差分约束有了更深的理解
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
/*
不等式*3
设前i头奶牛有斑点牛d[]个，设lr为给定区间
则：
1、每个区间有且只有一头奶牛有斑点=>d[r]-d[l-1]=1;
2、两只相邻的奶牛要么有斑点要么没斑点=>0<=d[i]-d[i-1]<=1;
改写方程得：
d[r]-d[l-1]<=1
d[l-1]-d[r]<=-1
d[i]-d[i-1]<=1
d[i-1]-d[i]<=0
于是：
l-1->r 1
r->l-1 -1
i-1->i 1
i->i-1 0
然后流氓优化+负环spfa卡过了这道题
*/
const int maxn=1e6+;
int n,m;
inline int read()
{
int x=,f=;char s=getchar();
while(s>''||s<''){if(s=='-')f=-;s=getchar();}
while(s<=''&&s>=''){x=x*+s-'';s=getchar();}
return x*f;
}
struct edge
{
int to,next,dis;
}e[maxn];
int head[maxn],cnt;
inline void addedge(int from,int to,int dis)
{
e[++cnt].next=head[from];
e[cnt].to=to;
e[cnt].dis=dis;
head[from]=cnt;
}
int dis[maxn],vis[maxn];
struct cmp
{
bool operator()(int a,int b)
{
return dis[a]>dis[b];
}
};
//queue < int > q;
int tot=;
priority_queue < int , vector < int > , cmp > q;
inline void spfa(int s)
{
/*for(int i=1;i<=n;i++)
{
dis[i]=2147483647;
}*/
memset(dis,0x7f,sizeof(dis));
q.push(s);
vis[s]=;
dis[s]=;
while(!q.empty())
{
int u=q.top();
q.pop();
vis[u]=;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(dis[v]>dis[u]+e[i].dis)
{
dis[v]=dis[u]+e[i].dis;
if(vis[v]==)
{
if(++tot>)
{
printf("-1");
exit();
}
q.push(v);
vis[v]=;
}
}
}
}
} int main()
{
n=read();m=read();//scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x,y;
x=read();y=read();//scanf("%d%d",&x,&y);
addedge(x-,y,);
addedge(y,x-,-);
}
for(int i=;i<=n;i++)
{
addedge(i,i-,);
addedge(i-,i,);
}
spfa();
printf("%d",dis[n]);
return ;
}