PRoblem Description

在古老的魔獸傳說中，有兩個軍團(tuán)，一個叫天災(zāi)，一個叫近衛(wèi)。在他們所在的地域，有n個隘口，編號為1..n，某些隘口之間是有通道連接的。其中近衛(wèi)軍團(tuán)在1號隘口，天災(zāi)軍團(tuán)在n號隘口。某一天，天災(zāi)軍團(tuán)的領(lǐng)袖巫妖王決定派兵攻打近衛(wèi)軍團(tuán)，天災(zāi)軍團(tuán)的部隊如此龐大，甚至可以填江過河。但是巫妖王不想付出不必要的代價，他想知道在不修建任何通道的前提下，部隊是否可以通過隘口及其相關(guān)通道到達(dá)近衛(wèi)軍團(tuán)展開攻擊。由于n的值比較大（n<=1000），于是巫妖王找到了擅長編程的你 =_=，請你幫他解決這個問題，否則就把你吃掉變成他的魔法。為了拯救自己，趕緊想辦法吧。

Input

輸入包含多組，每組格式如下。

第一行包含兩個整數(shù)n,m（分別代表n個隘口，這些隘口之間有m個通道）。

下面m行每行包含兩個整數(shù)a，b；表示從a出發(fā)有一條通道到達(dá)b隘口（注意：通道是單向的）。

Output

如果天災(zāi)軍團(tuán)可以不修建任何通道就到達(dá)1號隘口，那么輸出YES，否則輸出NO。

Example Input

2 11 22 12 1
Example Output
NOYES
 
#include<stdio.h>#include<stdlib.h>#define max 1001int df[max][max];int book[max];int queue[max];int front,rear,flag,n,m;void bfs(int x){    int i,j;    book[x]=1;    rear++;    queue[rear]=x;    if(x==1)    {        flag=1;        return ;    }    while(front!=rear)    {        front++;        i=queue[front];        for(j=1;j<=n;j++)        {            if(df[i][j]&&book[j]==0)            {                book[j]=1;                rear++;                queue[rear]=j;                if(j==1)                {                    flag=1;                    return ;                }            }        }    }}int main(){    int u,v;    while(scanf("%d%d",&n,&m)!=EOF)    {        front=rear=flag=0;        memset(df,0,sizeof(df));        memset(book,0,sizeof(book));        while(m--)        {            scanf("%d%d",&u,&v);            df[u][v]=1;        }        bfs(n);        if(flag)        {            printf("YES/n");        }        else        {            printf("NO/n");        }    }    return 0;}