1 #include<stdio.h>
2 #include<string.h>
3 int map[1000][1000],visit[1000];
4 int step,mark;
5 int queue[1000];//用来储存已经遍历了的数据。
6 void BFS(int k)
7 {
8 int i,o=0,p=0,temp,end=0;//temp用来表示当前所在地。o表示下一步从哪个顶点向下出发。
9 while(o<=p)//p表示在当前一层内有多少个顶点。
10 {
11 temp=queue[o];
12 for(i=1;i<=k;i++)
13 {
14 if(map[temp][i]==1&&visit[i]==0)
15 {
16 if(i==1){mark=1;return;}
17 queue[++p]=i;
18 visit[i]=1;
19 }
20 }
21 if(o==end)//此时表示该层的所有顶点已经遍历完毕。
22 {
23 step++;//每遍历完一层步数+1。
24 end=p;//将下一层最后一个顶点放入遍历顺序中。
25 }
26 o++;//遍历下个顶点。
27 }
28 }
29 int main()
30 {
31 int k,n;
32 while(scanf("%d %d",&k,&n)!=EOF)
33 {
34 mark=0;//用来标记是否达到近卫军团所在地。
35 step=1;//用来记录步数。
36 memset(map,0,sizeof(map));
37 memset(visit,0,sizeof(visit));
38 memset(queue,0,sizeof(queue));
39 int i,a,b;
40 for(i=0;i<n;i++)
41 {
42 scanf("%d %d",&a,&b);
43 map[a][b]=1;//单项路径。
44 }
45 visit[k]=1;//起点已经搜索过。
46 queue[0]=k;//k作为起点，先储存好。
47 BFS(k);
48 if(mark==1)printf("%d
",step);
49 else printf("NO
");
50 }
51 }
