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
135
136
137
//#define __DEBUG

#include <iostream>
#include <vector>
#include <set>

using namespace std;
#define REP(x,n) for(int x=0;x<(n);++x)
#define VAR(x,n) __typeof(n) x = (n)
#define FOREACH(x,n) for(VAR(x,(n).begin());x!=(n).end();++x)

int m,n;
const int MAX_N = 500001;
struct Node: vector<int> {
	int parent;
	int vis_nr;
	bool active;
	Node(): parent(-1), vis_nr(-1), active(false) {}
} g[MAX_N];

int minCycleLength = 1000000000;
int minCycleNode = -1;
int disabled=-1;

int cycle[MAX_N];

void printNodes(int youngest, int eldest) {
	int i=0;
	for(int x=youngest; x!=g[eldest].parent && x!=-1; x=g[x].parent)
#ifdef __DEBUG
	{
		cerr << x << " ";
		cycle[i++] = x;
	}
	cerr << endl;
#else
		cycle[i++] = x;
#endif
}

bool Dfs(int start, bool forceReturn=false) {
#ifdef __DEBUG
	cerr<<"Dfs "<<start<<"; vis_nr "<<g[start].vis_nr<<"; "<<g[start].size()<<" krawedzi"<<endl;
#endif
	if(start==disabled) {
#ifdef __DEBUG
		cerr<< "  disabled"<<endl;
#endif
		return false;
	}
	g[start].active = true;
	bool result=false;
	FOREACH(it, g[start])
		if(g[*it].vis_nr == -1) {
#ifdef __DEBUG
			cerr<<"  "<<*it<<" do odwiedzenia"<<endl;
#endif
			g[*it].vis_nr = g[start].vis_nr+1;
			g[*it].parent = start;
			if(Dfs(*it, forceReturn) && forceReturn) {
				result=true;
				break;
			}
		} else if (g[*it].active) {
			int cycleLength = g[start].vis_nr - g[*it].vis_nr + 1;
#ifdef __DEBUG
			cerr<<"  "<<*it<<" w cyklu"<<endl;
			cerr << "Cykl " << cycleLength << endl;
#endif
			result=true;
			if(forceReturn)
				break;
			if(cycleLength < minCycleLength) {
				minCycleLength = cycleLength;
				minCycleNode = start;
				printNodes(start, *it);
			}
		}
#ifdef __DEBUG
		 else
			cerr<<"  "<<*it<<" - nic szczegolnego"<<endl;
#endif
	g[start].active = false;
	return result;
}

bool Dfs(bool forceReturn=false) {
#ifdef __DEBUG
	cerr<<"##DFS## "<<forceReturn<<endl;
#endif
	REP(x,n)
		g[x].vis_nr = -1;
	REP(x,n)
		if(g[x].vis_nr == -1) {
			g[x].vis_nr = 0;
			if(Dfs(x, forceReturn) && forceReturn) {
#ifdef __DEBUG
				cerr << "##DFS returns true"<<endl;
#endif
				return true;
			}
		}
#ifdef __DEBUG
	cerr<<" ##DFS returns false"<<endl;
#endif
	return false;
}
bool hasCycle(int dis) {
#ifdef __DEBUG
	cerr<<"$$HasCycle$$ "<<dis<<endl;
#endif
	disabled = dis;
	return Dfs(true);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin>>n>>m;
	int a,b;
	REP(x,m) {
		cin>>a>>b;
		g[a-1].push_back(b-1);
	}
	Dfs();
	if(minCycleNode == -1) {
		cout<<"NIE";
	} else {
		set<int> result;
		REP(x, minCycleLength)
			if(!hasCycle(cycle[x]))
				result.insert(cycle[x]+1);
		cout<<result.size()<<endl;
		FOREACH(it, result)
			cout<<*it<<" ";
	}
	return 0;
}