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
#include <cstdio>
#include <stack>
#include <set>
using namespace std;

set<int> startCycle;
set<int> endCycle;
int bestRoads;

inline void findCycles(int n, stack<int> *edge, int startV)
{
	bool *visited = new bool [n+1]();
	bool *onStack = new bool [n+1]();
	onStack[startV] = true;
	visited[startV] = true;
	
	int v, nextV;
	stack <int> tmp;
	tmp.push(startV);

	while(!tmp.empty())
	{
		v = tmp.top();
		//printf("%d\n", v);
		if (edge[v].empty())
		{
			onStack[v] = false;
			tmp.pop();
		}
		else
		{
			nextV = edge[v].top();
			//printf("  %d\n", nextV);
			edge[v].pop();
			if (!visited[nextV])
			{
				visited[nextV] = true;
				onStack[nextV] = true;
				tmp.push(nextV);
			}
			else if (onStack[nextV])
			{
				startCycle.insert(nextV);
				endCycle.insert(v);
				//printf("CYCLE %d -> %d\n", nextV, v);
			}
		}
	}
	
	delete [] visited;
	delete [] onStack;
}

inline void findBestRoad(int n, stack<int> *edge, bool *bestRoad, int startV)
{
	bool *visited = new bool [n+1]();
	visited[startV] = true;
	
	int v, nextV;
	stack <int> tmp;
	tmp.push(startV);
	startCycle.erase(startV);
		
	while(!tmp.empty())
	{
		v = tmp.top();
		startCycle.erase(v);
		if (startCycle.empty())
		{
			bestRoad[v] = true;
			bestRoads++;
		}
		if (endCycle.find(v) != endCycle.end())
			return ;
		if (edge[v].empty())
			tmp.pop();
		else
		{
			nextV = edge[v].top();
			edge[v].pop();
			if (!visited[nextV])
			{
				visited[nextV] = true;
				tmp.push(nextV);
			}
		}
	}
	
	delete [] visited;
}

int main()
{
	int n, m, a, b;
	scanf("%d %d", &n, &m);
	stack <int> *edge1 = new stack<int>[n+1]();
	stack <int> *edge2 = new stack<int>[n+1]();
	
	for (int i=0; i<m; ++i)
	{
		scanf("%d %d", &a, &b);
		edge1[a].push(b);
		edge2[a].push(b);
	}
	
	int startV = 1;
	findCycles(n, edge1, startV);
	if (!startCycle.empty())
	{
		bool *bestRoad = new bool[n+1]();
	
		findBestRoad(n, edge2, bestRoad, startV);
		printf("%d\n", bestRoads);
		for (int i=1; i<=n; ++i)
			if (bestRoad[i])
				printf("%d ", i);
		printf("\n");
	}
	else
		printf("NIE\n");
	return 0;
}