Description
GBQC国一共有N个城市，标号分别为1, 2, …, N。N个城市间一共有M条单向通行的道路。
不幸的是，GBQC国的城市1连续暴雨，使得整个城市淹没在汪洋洪水中，于是GBQC国领导人小明决定让城市1的居民暂时移居到城市N，于是一场浩浩荡荡的搬迁运动开始了。
但还有一个问题需要解决，居民从城市1出发，如果走到某个城市时面对多条道路，那么城市1的居民就不知道该往哪个方向走了。
为了解决上述问题，GBQC国领导人决定在一些道路的入口处设置“禁止通行”的路障，以确保城市1的居民从城市1出发，途径每个城市时，都有且仅有一条路可供选择，这样城市1的居民就能顺利搬迁到城市N了。
现在GBQC国领导人想知道最少需要设置几个路障呢？
Input
输入包含多组测试数据。
对于每组测试数据，第一行包含两个整数N(2<=N<=10^4), M(0<=M<=10^5)，其中N、M的含义同上。接下来一共有M行，每行有三个整数x(1<=x<=N)、y(1<=y<=N)，表示GBQC国有一条由城市x进入通向城市y的单向道路。
Output
对于每组测试数据，用一行输出一个整数表示最少需要设置几个路障。如果没办法从城市1出发走到城市N，则输出“-1”（不包括引号）。
Sample Input
3 4 1 1 1 2 1 3 1 3 3 2 1 3 3 2 2 0
Sample Output
3 0 -1
Hint
由于数据量较大，推荐使用scanf和printf。
代码：
#include<cstdio>
#include<set>
using namespace std;
int du[10001];
set<int> s[10001];
bool flag[10001];
int dis[10001];
int n,m;
int main(){
while(scanf("%d %d",&n,&m) == 2){
int ans = -1;
for(int i = 1;i <= n;i++){
du[i] = -1;
flag[i] = false;
dis[i] = -1;
s[i].clear();
}
for(int i = 1;i <= m;i++){
int x,y;
scanf("%d %d",&x,&y);
du[x]++;
if(s[x].find(y) == s[x].end())
s[x].insert(y);
}
flag[1] = true;
int min_city = -1;
for(int i = 2;i <= n;i++){
if(s[1].find(i) != s[1].end()){
dis[i] = du[1];
min_city = i;
}
}
while(min_city != -1){
if(min_city == n){
ans = dis[n];
break;
}
flag[min_city] = true;
for(set<int>::iterator it = s[min_city].begin();it != s[min_city].end();it++){
if(!flag[*it]){
if(dis[*it] == -1) dis[*it] = dis[min_city] + du[min_city];
else if(dis[*it] > dis[min_city] + du[min_city]) dis[*it] = dis[min_city] + du[min_city];
}
}
min_city = -1;
int tempdis = 10000000;
for(int i = 2;i <= n;i++){
if(!flag[i] && dis[i] < tempdis && dis[i] != -1){
min_city = i;
tempdis = dis[i];
}
}
}
printf("%d
",ans);
}
return 0;
}