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
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>

using namespace std;

const int N = 500005;

int n, m, a, b, size[2], intervalBegin, intervalEnd;
int vis[N], S[2][N], where[N];
vector<int>V[2][N];
int visited;
int specjal;

void DFS(int w, int d) {
    vis[w] = 1;
    visited++;
    
    for (int i = 0; i < V[d][w].size(); i++) {
        int u = V[d][w][i];
        if (vis[u] == 0) {
            DFS(u, d);
        } else if (vis[u] == 2 && d == 1) {
            swap(V[d][w][i], V[d][w].back());
            V[d][w].pop_back();
            i--;
        }
    }
    S[d][++size[d]] = w;   
 }

bool isCycle() {
    for (int i = 1; i <= n; i++) {
        vis[i] = 0;
    }
    size[0] = size[1] = 0;
    vis[specjal] = 1;
    for (int i = 1; i <= n; i++) {
        if (vis[i] == 0) {
            DFS(i, 0);
        }
    }
    
    
    for (int i = 1; i <= n; i++) {
        vis[i] = 0;
    }
    vis[specjal] = 1;
    
    visited = 0;
    bool ret = false;
    for (int i = size[0]; i >= 1; i--) {
        int lastVisited = visited;
        if (vis[S[0][i]] == 0) {
            int lSize = size[1];
            DFS(S[0][i], 1);
            for (int j = lSize + 1; j <= size[1]; j++) {
                vis[S[1][j]] = 2;
            }
            if (visited > lastVisited + 1) {
                ret = true;
            }
        }
    }
    
    return ret;
}

vector<int> results;

int best[N];

void findNodes() {
    
    reverse(S[1] + 1, S[1] + 1 + size[1]);
    for (int i = 1; i <= size[1]; i++) {
        where[S[1][i]] = i;
    }
    
    intervalEnd = 1e9;
    for (int i = 1; i <= size[1]; i++) {
        int w = S[1][i];
        for (int j = 0; j < V[1][w].size(); j++) {
            int u = V[1][w][j];
            if (where[u] != 0 && where[u] < where[w]) {
                intervalBegin = max(intervalBegin, where[u]);
                intervalEnd = min(intervalEnd, where[w]);
            }
        }
    }
    
    if (intervalEnd < intervalBegin) {
        return;
    }
    
    int maxi = 1e9;    
    for (int i = size[1]; i >= 1; i--) {
        int w = S[1][i];
        if ((maxi >= i) && (intervalBegin <= i && i <= intervalEnd)) {
            results.push_back(w);
        }
        
        best[w] = 1e9;
        
        for (int j = 0; j < V[1][w].size(); j++) {
            int u = V[1][w][j];
            if (where[u] != 0 && i < where[u]) {
                best[w] = min(best[w], best[u]);
            } else if (where[u] != 0 && where[u] < i) {
                best[w] = min(best[w], where[u]);
            }
        }
        
        for (int j = 0; j < V[0][w].size(); j++) {
            int u = V[0][w][j];
            if (where[u] != 0 && where[u] < i && where[u] >= best[w]) {
                maxi = min(maxi, where[u]);
            }
        }
    }
}

int main() {
    
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &a, &b);
        V[0][b].push_back(a);
        V[1][a].push_back(b);
    }
    
    if (!isCycle()) {
        printf("NIE\n");
        return 0;
    }

    findNodes();
    
    printf("%d\n", results.size());
    sort(results.begin(), results.end());
    for(int i = 0; i < results.size(); i++) {
        printf("%d ", results[i]);
    }
    
    return 0;
}