GBQC国一共有N个城市，标号分别为1, 2, …, N。N个城市间一共有M条单向通行的道路。

现在GBQC国领导人想知道最少需要设置几个路障呢？

3 4
1 1
1 2
1 3
1 3

3 2
1 3
3 2

2 0

3
0
-1

```#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
struct node
{
int end;
int dis;
bool friend operator <(node a,node b)
{
return a.dis > b.dis;
}
};
const int MAX = 10010;
int n,m;
int dis[MAX];
int degree[MAX];
vector <int> v[MAX];
void dijkstra()
{
int i;
for(i = 1;i <= n; i++)
dis[i] = 0x7fffffff;
dis[1] = 0;
node t;
t.end = 1;
t.dis = 0;
priority_queue <node> q;
q.push(t);
while(!q.empty())
{
t = q.top();
q.pop();
int len = v[t.end].size();
for(i = 0;i < len; i++)
{
node tt;
int k = v[t.end][i];
if(dis[k] > t.dis + v[t.end].size() - 1)
{
dis[k] = t.dis + v[t.end].size() - 1;
tt.end = k;
tt.dis = dis[k];
q.push(tt);
}
}
}
}
int main()
{
node x;
int s,e,i;
while(scanf("%d %d",&n,&m)!=EOF)
{
//memset(degree,0,sizeof())
for(i = 1;i <= n; i++)
v[i].clear();
while(m--)
{
scanf("%d %d",&s,&e);
v[s].push_back(e);
}
dijkstra();
if(dis[n] == 0x7fffffff)
puts("-1");
else
printf("%d\n",dis[n]);
}
return 0;
}
```