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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
// Karol Kosinski
#include <cstdio>
#include <algorithm>
#include <list>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
//#define DEBUG(x...) printf(x)
#define DEBUG(x...)
using namespace std;
const int NX = 500003;
const int WHITE = 0;
const int GREY = -1;

struct vertex {
        int color;
        list<int> adj;
};

int n, m, c, r;
bool Critical[NX];
int Cycle[NX], Res[NX], Value[NX];
vertex G[NX];

void read_data() {
        scanf("%d%d", &n, &m);
        FOR(i,1,m) {
                int a, b;
                scanf("%d%d", &a, &b);
                G[a].adj.push_back(b);
        }
}

bool dfs_for_cycles(int s) {
        G[s].color = GREY;
        for( int v : G[s].adj ) {
                if( G[v].color == WHITE and dfs_for_cycles(v) ) {
                        Cycle[++c] = s;
                        DEBUG("*** (%d, %d)\n", s, v);
                        return true;
                } else if( G[v].color == GREY ) {
                        Cycle[++c] = v;
                        Cycle[++c] = s;
                        DEBUG("*** (%d, %d)\n", s, v);
                        return true;
                }
        }
        G[s].color = s;
        return false;
}

bool find_a_cycle(int v_to_remove) {
        FOR(i,1,n)
                G[i].color = WHITE;
        G[v_to_remove].adj.clear();
        c = 0;
        FOR(i,1,n)
                if( dfs_for_cycles(i) )
                        return true;
        return false;
}

void remove_edges_from_the_cycle() {
        Res[1] = Cycle[1];
        FOR(i,2,c) {
                Res[i] = Cycle[i];
                if( Res[i] == Res[1] ) {
                        r = i - 1;
                        break;
                }
        }
        reverse(Res + 1, Res + r + 2);
        DEBUG("Cycle found:\n");
        FOR(i,1,r) {
                G[Res[i]].adj.remove(Res[i+1]);
                DEBUG("%d-%d ", Res[i], Res[i+1]);
        }
        DEBUG("\n");
}

inline void assign_smaller_value(int &mx, int cur) {
        if( Value[cur] < Value[mx] )
                mx = cur;
}

inline void assign_bigger_value(int &mx, int cur) {
        if( Value[cur] > Value[mx] )
                mx = cur;
}

int dfs_for_validation(int s) {
        G[s].color = GREY;
        int min_col = NX - 1, max_col = 0, col;
        DEBUG("** v: %d\n", s);
        for( int v : G[s].adj ) {
                if( Value[v] > 0 )
                        col = v;
                else if( G[v].color == WHITE )
                        col = dfs_for_validation(v);
                else if( G[v].color != GREY )
                        col = G[v].color;
                else
                        continue;
                DEBUG("==== (%d, %d): %d\n", s, v, col);
                assign_smaller_value(min_col, col);
                assign_bigger_value(max_col, col);
        }
        if( min_col < NX - 1 )
                G[s].color = min_col;
        DEBUG("## v: %d\tcol: %d\tret: %d\n", s, G[s].color, max_col);
        return max_col;
}

bool validate_vertices_of_the_cycle() {
        FOR(i,1,r) {
                Critical[Res[i]] = true;
                Value[Res[i]] = i;
        }
        int ban_until = 0;
        auto verify_vertex = [&ban_until](int j) {
                if( ban_until == j )
                        ban_until = 0;
                if( ban_until > 0 )
                        Critical[j] = false;
        };
        FOR(i,1,n)
                G[i].color = WHITE;
        Value[NX - 1] = NX - 1;
        DEBUG("\nValidation:\n");
        FOR(i,1,r) {
                int j = Res[i];
                verify_vertex(j);
                Value[j] += r;
                int v = dfs_for_validation(j);
                DEBUG("+++++++++ %d --> %d (ban)\n\n", j, v);
                assign_bigger_value(ban_until, v);
        }
        FOR(i,1,r)
                verify_vertex(Res[i]);
}

bool list_the_candidates() {
        r = 0;
        DEBUG("Candidates:\n");
        FOR(i,1,n)
                if( Critical[i] ) {
                        Res[++r] = i;
                        DEBUG("%d ", i);
                }
        DEBUG("\n");
        return ( r > 0 );
}

void write_result() {
        printf("%d\n", r);
        FOR(i,1,r)
                printf("%d ", Res[i]);
        printf("\n");
}

int main() {
        read_data();
        if( not find_a_cycle(0) ) {
                printf("NIE\n");
                return 0;
        }
        remove_edges_from_the_cycle();
        validate_vertices_of_the_cycle();
        if( list_the_candidates() and find_a_cycle(Res[1]) )
                r = 0;
        write_result();
        return 0;
}