#include <iostream> #include <cstdio> #include <cstring> #include <vector> 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++; } vector<int> ans; void dfs(int x) { ans.push_back(x); if(x==e) return; 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(n==1&&!m) { printf("%d\n",n); continue; } 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&°c[i]==1) s=i; else if(!degc[i]&&e==-1&°r[i]==1) e=i; else { flag=false; break; } } ans.clear(); if(!flag) puts("NO"); else { dfs(s); printf("%d",ans[0]); for(int i=1;i<ans.size();i++) printf(" %d",ans[i]); putchar('\n'); } } return 0; } |
Double click to view unformatted code.