Description

    奶牛们接到了寻找一种新型挤奶机的任务，为此它们准备依次经过N(1≤N≤50000)颗行星，在行星上进行交易．为了方便，奶牛们已经给可能出现的K(1≤K≤1000)种货物进行了由1到K的标号．由于这些行星都不是十分发达．没有流通的货币，所以在每个市场里都只能用固定的一种货物去换取另一种货物．    奶牛们带着一种上好的饲料从地球出发，希望进行最少的交易，最终得到所需要的机器．饲料的标号为1，所需要的机器的标号为K.如果任务无法完成，输出-1.

Input

    第1行是两个数字N和K.

    第2到N+1行，每行是两个数字Ai和Bi，表示第i颗行星愿意提供Ai为得到Bi．

Output

    第1行输出最小交换次数

Sample Input

6 5

1 3

3 2

2 3

3 1

2 5

5 4

Sample Output

4

 

 

bfs不解释……

#include
      
       #include
       
        #include
        
         using namespace std;struct na{    int y,ne;    na(){        ne=0;    }};int n,k,a,l[1001],r[1001],x,y,dis[1001],i;na b[50001];queue 
         
           q;char cc;int read(){    int a=0;    cc=getchar();    while(cc<'0'||cc>'9') cc=getchar();    while(cc>='0'&&cc<='9') a=a*10+cc-48,cc=getchar();    return a;}int main(){    n=read();k=read();    for (i=1;i<=n;i++){        x=read();y=read();        if (l[x]==0) l[x]=i;else b[r[x]].ne=i;        r[x]=i;b[i].y=y;    }    for (i=1;i<=k;i++) dis[i]=1001;    q.push(1);dis[1]=1;    while(!q.empty()){        int p=q.front();        for (i=l[p];i;i=b[i].ne){            if (dis[b[i].y]==1001){                if (b[i].y==k){                    printf("%d",dis[p]+1);                    return 0;                }                dis[b[i].y]=dis[p]+1;                q.push(b[i].y);            }        }        q.pop();    }    printf("-1");}