View Code of Problem 3847

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<stack>
#include<cmath>
using namespace std;

typedef long long ll;
const int N = 2e5+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);
    for(int i=head[from];i;i=edge[i].pre){
        int to = edge[i].to;
        dfs(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;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);
        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()>=2||endd.size()>=2||flag){
            printf("NO\n");
            continue;
        }
        res.clear();
        dfs(start[0]);
        for(int i=0;i<res.size();i++){
            if(i!=res.size()-1)
                printf("%d ",res[i]);
            else
                printf("%d\n",res[i]);
        }
    }
}