#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<stack> #include<cmath> using namespace std; typedef long long ll; const int N = 1e5+10; int n,m; int in[N],out[N]; typedef struct { int from,to,pre; }node; node edge[N]; int head[N]; int tot; vector<int>res; void Add_edge(int from,int to){ edge[tot].from=from; edge[tot].to=to; edge[tot].pre=head[from]; head[from]=tot++; } void dfs(int from){ res.push_back(from); if(head[from]!=0) dfs(edge[head[from]].to); } int main() { #ifdef ACM_LOCAL freopen("./std.in", "r", stdin); #endif int t,a,b; scanf("%d",&t); for(int Case=1;Case<=t;Case++){ scanf("%d%d",&n,&m); tot=1; for(int i=1;i<=n+10;i++) in[i]=out[i]=head[i]=0; for(int i=1;i<=m;i++){ scanf("%d%d",&a,&b); Add_edge(a,b); in[b]++;out[a]++; } printf("Case #%d:\n",Case); if(n-1!=m){ printf("NO\n"); continue; } if(n==1&&m==0){ printf("1\n"); continue; } bool flag=0; vector<int>start; vector<int>endd; for(int i=1;i<=n;i++){ if(in[i]==0&&out[i]==1){ start.push_back(i); }else if(in[i]==1&&out[i]==0){ endd.push_back(i); }else if(in[i]==1&&out[i]==1){ continue; }else{ flag=1; break; } } if(start.size()!=1||endd.size()!=1||flag){ printf("NO\n"); continue; } res.clear(); dfs(start[0]); if(res.size()!=n) { printf("NO\n"); continue; } for(int i=0;i<res.size();i++){ if(i!=res.size()-1) printf("%d ",res[i]); else printf("%d\n",res[i]); } } } |
Double click to view unformatted code.