代码

#include <bits/stdc++.h>
using namespace std;
vector <int> a[200010];
int m,n,c=0,r[200010],o;
void dfs(int l){
	for(int i=0;i<a[l].size();i++){
		if(a[l][i]!=0){
			int p=a[l][i];
			a[l][i]=0;
			dfs(p);
		}
	}
	c++;
	r[c]=l;
	return;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>m;
	int dx[100010]={0},dy[100010]={0};
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		a[x].push_back(y);
		dx[x]++;
		dy[y]++;
	}
	int q=-1,l=1,l1=1,t=-1;
	for(int i=1;i<=n;i++){
		sort(a[i].begin(),a[i].end());
	}
	for(int i=1;i<=n;i++){
        if(dx[i]==dy[i]+1&&l==1){
	       	q=i;
	       	l=0;
		}
		else{
	        if(dx[i]==dy[i]-1&&l1==1){
	        		l1=0;
	        		t=i;
			}
			else{
				if(dx[i]!=dy[i]){
					cout<<"NO";
					return 0;			
				}
			}
		}
    }
    if(q==-1||t==-1){
    	cout<<"NO";
    	return 0;
	}
	for(int i=n;i>1;i--){
		if(i!=q&&i!=t&&dx[i]!=dy[i]){
			cout<<"NO";
			return 0;
		}
	}
	dfs(q);
	for(int i=c;i>=1;i--){
		cout<<r[i]<<" ";
	}
	return 0;
}