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

int m, n, a, b;
vector<vector<int> > adj_in, adj_out;

// *******************************************************************************

vector<bool> on_path;
int avoid_vertex;
vector<int> adj_start;

bool dfs(int v)
{
    if (on_path[v])
    {
//        printf("Znaleziono cykl z wierzcholkow: ");
//        for(int i=0; i<n; ++i) if (on_path[i]) printf("%d ", i+1);
//        printf("\n");
        return true;
    }
    on_path[v] = true;
//    printf("-> PUSH(%d)\n", v+1);
    while (adj_start[v] != adj_out[v].size())
    {
        int next_v = adj_out[v][adj_start[v]]; ++adj_start[v];
//        printf("next_v = %d\n", next_v+1);
        if (next_v == avoid_vertex) continue;
        if (dfs(next_v)) return true;
    }
//    printf("-> POP(%d)\n", v+1);
    on_path[v] = false;
    return false;
}

bool is_acyclic()
{
//    printf("Sprawdzamy acyklicznosc. Unikamy %d\n", avoid_vertex + 1);
    on_path.clear();   on_path.resize(n, false);
    adj_start.clear(); adj_start.resize(n, 0);
    for(int i=0; i<n; ++i)
    {
        if (i==avoid_vertex) continue;
//        printf("Sprawdzamy startujac z %d\n", i+1);
        if (dfs(i)) return false;
    }
//    printf("Koniec sprawdzania\n");
    return true;
}

// *******************************************************************************

int main()
{
    scanf("%d %d", &n, &m);
    adj_in.resize(n);
    adj_out.resize(n);

    for(int i=0; i<m; ++i)
    {
        scanf("%d %d", &a, &b); --a; --b;
        adj_out[a].push_back(b);
        adj_in[b].push_back(a);
    }

/*
    for(int i=0; i<n; ++i)
    {
        printf("%d: ", i+1);
        for(int j=0; j<adj_out[i].size(); ++j) printf("%d ", adj_out[i][j]+1);
        printf("\n");
    }
*/

    avoid_vertex = -1;
    if (is_acyclic())
    {
        printf("NIE\n");
        return 0;
    }

    vector<int> result;
    for(int i=0; i<n; ++i)
    {
        if (adj_in[i].empty() || adj_out[i].empty()) continue;
        avoid_vertex = i;
        if (is_acyclic()) result.push_back(i);
    }

    printf("%d\n", result.size());
    if (!result.empty())
    {
        for(int i=0; i<result.size(); ++i) printf("%d ", result[i]+1);
        printf("\n");
    }
}