1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<iostream>
#include<vector>
#include<algorithm>
#define pb push_back
using namespace std;
vector<int>v[1000001],t[1000001],sciezka,res;
bool odw[1000001];
int nie[1000001],na_sc[1000001],najd,ost,len,w_wyn[1000001];
bool zeg;
vector<int>zabr;
int n,m;
vector<pair<int,int> >zle;
void start(int x,vector <int> *g){
	odw[x]=1;
	if(na_sc[x]!=-1){
		if(zeg){
			if(ost<na_sc[x]){
				zle.pb(make_pair(ost+1,na_sc[x]-1));
				//cout<<"zle "<<ost+1<<" "<<na_sc[x]-1<<"\n";
			}
			zabr.pb(sciezka[(na_sc[x]+1)%len]);
		}
		else{
			if(ost<na_sc[x]){
				zle.pb(make_pair(na_sc[x]+1,ost-1));
				//cout<<"zle "<<na_sc[x]+1<<" "<<ost-1<<"\n";
			}
			zabr.pb(sciezka[(na_sc[x]-1+len)%len]);	
		}
	}
	for(int i=0;i<g[x].size();i++){
		if(zabr[zabr.size()-1]==g[x][i]||odw[g[x][i]])continue;
		start(g[x][i],g);
	}
	if(na_sc[x]!=-1)zabr.pop_back();
}
int f(){
	zeg=1;
	for(int i=0;i<len;i++){
		if(!odw[sciezka[i]]){
			ost=i;
			start(sciezka[i],v);	
		}
	}
	zeg=0;
	//cout<<"--\n";
	for(int i=0;i<n;i++)odw[i]=0;
	for(int i=0;i<len;i++){
		if(!odw[sciezka[i]]){
			ost=i;
			start(sciezka[i],t);
		}
	}
}
int koncz;
int vis[1000000];
bool cykl(int x){
	vis[x]=1;
	for(int i=0;i<v[x].size();i++){
		if(vis[v[x][i]]==2||w_wyn[v[x][i]])continue;
		if(vis[v[x][i]]==1){
			koncz=v[x][i];
			sciezka.pb(x);
			return 1;
		}
		if(cykl(v[x][i])){
			if(koncz!=-1)sciezka.pb(x);
			if(x==koncz)koncz=-1;	
			return 1;
		}
	}
	vis[x]=2;
	return 0;
}
main(){
	ios_base::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=0;i<2*n;i+=2){
		v[i].pb(i+1);
		t[i+1].pb(i);
	}
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		v[2*a+1].pb(2*b);
		t[2*b].pb(2*a+1);
	}
	n*=2;
	koncz=-1;
	for(int i=0;i<n;i++){
		if(!vis[i]&&sciezka.size()==0)cykl(i);	
	}
	if(sciezka.size()==0){
		cout<<"NIE\n";
		return 0;	
	}
	for(int i=0;i<n;i++)na_sc[i]=-1;
	len=sciezka.size();
	for(int i=0;i<(len)/2;i++)swap(sciezka[i],sciezka[len-1-i]);
	//for(int i=0;i<len;i++)cout<<sciezka[i]<<" ";
	//cout<<"\n";
	for(int i=0;i<len;i++)na_sc[sciezka[i]]=i;
	f();
	for(int i=0;i<zle.size();i++){
		zle[i].first=(zle[i].first+len)%len;
		zle[i].second=(zle[i].second+len)%len;
		if(zle[i].first>zle[i].second){
			zle.push_back(make_pair(zle[i].first,len-1));
			zle[i].first=0;
		}
	}
	sort(zle.begin(),zle.end());
	int it=0;
	for(int i=0;i<zle.size();i++){
		while(it<zle[i].first){
			res.pb(sciezka[it++]);	
		}
		it=max(it,zle[i].second+1);
	}
	while(it<len)res.pb(sciezka[it++]);
	for(int i=0;i<res.size();i++)w_wyn[res[i]]=1;
	for(int i=0;i<n;i++)vis[i]=0;
	for(int i=0;i<n;i++){
		if(!w_wyn[i]&&vis[i]==0&&cykl(i)){
			cout<<0<<"\n";
			return 0;	
		}
	}
	sort(res.begin(),res.end());
	cout<<res.size()/2<<"\n";
	for(int i=0;i<res.size();i+=2)cout<<res[i]/2+1<<" ";
	cout<<"\n";
}