#include <iostream> #include <cstdio> #include <cstring> using namespace std; int n,m; int degc[10010]; int degr[10010]; struct edge{ int v,next; }; edge E[10010]; int head[10010]; int ne; int s,e; void addedge(int a,int b) { E[ne].v=b; E[ne].next=head[a]; head[a]=ne++; } void dfs(int x) { if(x==s) printf("%d",s); else if(x==e) { printf(" %d\n",e); return; } else printf(" %d",x); for(int i=head[x];i!=-1;i=E[i].next) dfs(E[i].v); } int main() { int t; scanf("%d",&t); int kase=0; while(t--) { ne=0; memset(head,-1,sizeof(head)); memset(degr,0,sizeof(degr)); memset(degc,0,sizeof(degc)); scanf("%d%d",&n,&m); int a,b; for(int i=0;i<m;i++) { scanf("%d%d",&a,&b); degc[a]++; degr[b]++; addedge(a,b); } printf("Case #%d:\n",++kase); if(!m) { puts("NO"); continue; } bool flag=true; s=-1,e=-1; for(int i=1;i<=n;i++) { if(degr[i]==1&°c[i]==1) continue; else if(!degr[i]&&s==-1) s=i; else if(!degc[i]&&e==-1) e=i; else { flag=false; break; } } if(!flag) puts("NO"); else { dfs(s); } } return 0; } |
Double click to view unformatted code.