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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <utility>
#include <stack>

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define MP make_pair
#define FOR(v,p,k) for(auto v=(p);v<=(k);++v)
#define FORD(v,p,k) for(auto v=(p);v>=(k);--v)
#define REP(i,n) for(auto i=0;i<(n);++i)
#define VAR(v,i) __typeof(i) v=(i)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define PB push_back
#define ST first
#define ND second
#define SIZE(x) (int)x.size()
#define ALL(c) c.begin(),c.end()

#define ODD(x) ((x)%2)
#define EVEN(x) (!(ODD(x)))

#define VERTEX_OUT_OF_GRAPH 9999999
// http://www-users.mat.umk.pl/~stencel/acm/algorytmika_praktyczna.pdf

template <class V, class E> struct Graph {
    // Typ krawędzi (Ed) dziedziczy po typie zawierającym dodatkowe informacje
    // związane z krawędzią (E). Zawiera on również pole v, określające numer
    // wierzchołka, do którego prowadzi krawędź. Zaimplementowany konstruktor
    // pozwala na skrócenie zapisu wielu funkcji korzystających ze struktury grafu.
    struct Ed : E {
        int v;
        Ed(E p, int w) : E(p), v(w) { }
    };
    // Typ wierzchołka (Ve) dziedziczy po typie zawierającym dodatkowe informacje
    // z nim związane (V) oraz po wektorze krawędzi. To drugie dziedziczenie może
    // wydawać się na pierwszy rzut oka stosunkowo dziwne, lecz jest ono przydatne -
    // umożliwia łatwe iterowanie po wszystkich krawędziach wychodzących z
    // wierzchołka v: FOREACH(it, g[v])
    struct Ve : V, vector<Ed> { };
    // Wektor wierzchołków w grafie
    vector<Ve> g;
    // Konstruktor grafu - przyjmuje jako parametr liczbę wierzchołków
    Graph(int n = 0) : g(n) { }
    // Funkcja dodająca do grafu nową krawędź skierowaną z wierzchołka b do e,
    // zawierającą dodatkowe informacje określone przez zmienną d.
    inline void EdgeD(int b, int e, E d = E()) {
        g[b].PB(Ed(d, e));
    }

    vector<int> nonTrivialScc;
    int topo;
    // Funkcja wykonująca algorytm DFS z wierzchołka v i aktualizująca wartości
    // zmiennych t
    void TopoDfs(int v) {
        // Jeśli wierzchołek nie był odwiedzony, to należy go odwiedzić
        if (!g[v].t) {
            // Zaznacz wierzchołek jako odwiedzony
            g[v].t = 1;
            // Odwiedź wszystkie wierzchołki, do których prowadzi krawędź z v
            FOREACH(it, g[v]) TopoDfs(it->v);
            // Zaktualizuj wartość t przetwarzanego wierzchołka
            g[v].t = --topo;
        }
    }
    // Właściwa funkcja implementująca sortowanie topologiczne
    inline void TopoSort(int withoutVertex) {
        FOREACH(it, nonTrivialScc) g[*it].t = 0;
        topo = SIZE(g);
        g[withoutVertex].t = topo;
        // Odwiedź wszystkie wierzchołki w grafie
        FOREACH(it, nonTrivialScc) TopoDfs(*it);
    }

    // Funkcja sprawdzająca, czy dany graf skierowany jest acykliczny
    inline bool AcyclicD(int withoutVertex) {
        // Wyznacz sortowanie topologiczne
        TopoSort(withoutVertex);
        // Dla każdej krawędzi w grafie sprawdź, czy prowadzi ona od wierzchołka
        // wcześniejszego do wierzchołka późniejszego w porządku topologicznym
        topo = SIZE(g);

        FOREACH(node_it, nonTrivialScc) {
            auto it = g.begin() + *node_it;
            if (it->t != topo) FOREACH(it2, *it) if (it->t >= g[it2->v].t) return false;
        }
        return true;
    }

    // Zmienna nr w pierwszej fazie algorytmu używana jest do pamiętania czasu
    // odwiedzania wierzchołków, natomiast w drugiej fazie algorytmu do numerowania
    // silnie spójnych składowych
    int nr;
    // Funkcja rekurencyjna, przeszukująca poddrzewo wierzchołka v. Jest ona
    // używana do realizacji obu faz przeszukiwania DFS
    void SccSDfs(int v) {
        // Jeśli wierzchołek nie był odwiedzony, to go odwiedź
        if (g[v].t == -1) {
            g[v].t = nr;
            // Odwiedź wszystkie wierzchołki, do których prowadzi krawędź z v
            FOREACH(it, g[v]) SccSDfs(it->v);
            // Jeśli wykonywana jest pierwsza faza algorytmu, to ustaw zmienną t
            // wierzchołka na czas przetworzenia (odejmowanie wartości 3 gwarantuje
            // przydzielanie numerów poczynając od 0 wzwyż)
            if (nr < 0) g[v].t = -(--nr) - 3;
        }
    }
    // Właściwa funkcja, wykonująca wyznaczanie silnie spójnych składowych
    void SccS() {
        // Zbuduj graf transponowany gt oraz ustaw wartości zmiennych t
        // wierzchołków na -1 (nieodwiedzone)
        Graph<V, E> gt(SIZE(g));
        REP(x, SIZE(g)) {
            g[x].t = gt.g[x].t = -1;
            FOREACH(it, g[x]) gt.EdgeD(it->v, x);
        }
        gt.nr = -2;
        nr = 0;
        VI v(SIZE(g));
        // Wykonaj pierwszą fazę przeszukiwania w głąb na grafie transponowanym oraz
        // wypełnij wektor v numerami wierzchołków w kolejności rosnących czasów
        // przetworzenia DFS
        REP(x, SIZE(g)) {
            gt.SccSDfs(x);
            v[gt.g[x].t] = x;
        }
        // Wykonaj drugą fazę przeszukiwania w głąb na oryginalnym grafie.
        FORD(x, SIZE(g) - 1, 0) {
            SccSDfs(v[x]);
            nr++;
        }
    }

};

struct VertexT { int t; };
struct EdgeT {};


int main() {
    int n, m, a , b;
    scanf("%d %d", &n, &m);
    Graph<VertexT, EdgeT> graph(n);
    REP(i, m) {
        scanf("%d %d", &a, &b);
        --a; --b;
        graph.EdgeD(a, b);
    }
    graph.SccS();
    VVI sccToVertices(n);
    REP(i, n) {
        sccToVertices[graph.g[i].t].PB(i);
    }
    int nonTrivialScc = -1;
    REP(i, n) {
        if (sccToVertices[i].size() > 1) {
            if (nonTrivialScc != -1) {
                printf("0\n\n");
                return 0;
            }
            nonTrivialScc = i;
        }
    }
    if (nonTrivialScc == -1) {
        printf("NIE\n");
        return 0;
    }
    graph.nonTrivialScc = sccToVertices[nonTrivialScc];
    FOREACH(it, graph.nonTrivialScc) {
        auto &neighs = graph.g[*it];
        FORD(i, SIZE(neighs)-1, 0) {
            if (graph.g[neighs[i].v].t != nonTrivialScc) {
                swap(neighs[i],neighs.back());
                neighs.pop_back();
            }
        }
    }

    VI res; res.reserve(n);
    FOREACH(it, graph.nonTrivialScc) {
        if (graph.AcyclicD(*it)) {
            res.PB(*it);
        }
    }
    int res_size = SIZE(res);
    printf("%d\n", res_size);
    REP(i, res_size) {
        printf("%d%s", res[i]+1, (((i+1)==res_size) ? "" : " "));
    }
    printf("\n");

    return 0;
}