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
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 500000;

int n, m, a, b;
bool blocked[MAXN + 5], vis[MAXN + 5];
vector <int> G[MAXN + 5];
vector <int> res;

bool cycle_from(int v);

int main() {
    scanf("%d %d", &n, &m); 
    for(int i = 0; i < m; ++i) {
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
    }
    bool is_cycle = false;
    for(int i = 1; i <= n; ++i) {
        if(cycle_from(i)) {
            is_cycle = true;
            break;
        }
    }
    if(!is_cycle) {
        printf("NIE\n");
        return 0;
    }
    for(int i = 1; i <= n; ++i) {
        blocked[i] = true;
        bool no_cycle = true;
        for(int j = 1; j <= n; ++j) {
            if(j == i) continue;
            if(cycle_from(j)) {
                no_cycle = false;
                break;
            }
        }
        if(no_cycle) res.push_back(i);
        blocked[i] = false;
    }
    printf("%d\n", res.size());
    sort(res.begin(), res.end());
    for(int i = 0; i < res.size(); ++i) {
        printf("%d ", res[i]);
    }
    return 0;
}

bool cycle_from(int v) {
    for(int i = 1; i <= n; ++i) vis[i] = false;
    queue <int> Q;
    Q.push(v);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        if(vis[u] && u == v) return true;
        for(int i = 0; i < G[u].size(); ++i) {
            if(!vis[G[u][i]] && !blocked[G[u][i]]) {
                vis[G[u][i]] = true;
                Q.push(G[u][i]);
            }
        }
    }
    return false;
}