1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<map> 9 #include<stack>10 using namespace std;11 12 const int maxn=20000+5;13 14 int n,m;15 16 vector<int> G[maxn];17 int in[maxn];18 int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;19 int fa[maxn];20 21 22 int find(int u,int v)23 {24     while(fa[u]!=v)25     {26         in[u]++;27         if(in[u]>1)  return 0;28         u=fa[u];29     }30     return 1;31 }32 33 int dfs(int u)34 {35     pre[u]=lowlink[u]=++dfs_clock;36     for(int i=0;i<G[u].size();i++)37     {38         int v=G[u][i];39         if(!pre[v])40         {41             fa[v]=u;42             if(!dfs(v)) return 0;43             lowlink[u]=min(lowlink[u],lowlink[v]);44         }45         else if(!sccno[v])46         {47             lowlink[u]=min(lowlink[u],pre[v]);48             if(!find(u,v))  return 0;49         }50     }51     if(lowlink[u]==pre[u])52     {53         scc_cnt++;54         if(scc_cnt>1)   return 0;55     }56     return 1;57 }58 59 int find_scc()60 {61     dfs_clock=scc_cnt=0;62     memset(sccno,0,sizeof(sccno));63     memset(pre,0,sizeof(pre));64     memset(in,0,sizeof(in));65     memset(fa,0,sizeof(fa));66     for(int i=0;i<n;i++)67         if(!pre[i])  if(!dfs(i))  return 0;68     return 1;69 }70 71 int main()72 {73     //freopen("D:\\input.txt","r",stdin);74     int T;75     scanf("%d",&T);76     while(T--)77     {78         scanf("%d",&n);79         for(int i=0;i<n;i++)  G[i].clear();80         while(true)81         {82             int u,v;83             scanf("%d%d",&u,&v);84             if(u==0 && v==0)  break;85             G[u].push_back(v);86         }87         if(find_scc() && scc_cnt==1)   cout<<"YES"<<endl;88         else cout<<"NO"<<endl;89     }90     return 0;91 }