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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class kon {

    static class Node {
        final int value;
        List<Node> edges = new ArrayList<>();

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(value + " => ");
            for (Node x: edges) {
                sb.append(x.value + " ");
            }
            return sb.toString();
        }
    }

    static class Graph {
        final int size;
        Node[] nodes;

        public Graph(int size) {
            this.size = size;
            nodes = new Node[size + 1];
            for (int i=1; i<=size; i++) nodes[i] = new Node(i);
        }

        void connect(int source, int target) {
            nodes[source].edges.add(nodes[target]);
        }

        @Override
        public String toString() {
            return Arrays.toString(nodes).replaceAll(",", "\n");
        }
    }

    static int n;
    static int m;

    static int currentName = 1;

    static int[] name;
    static boolean[] onStack;
    static int[] parent;
    static int cyclesCounter = 0;
    static boolean hasCycle = false;
    static boolean hasAtLeastOneCycle = false;
    static List<List<Integer>> answer = new ArrayList<>();

    static void init() {
        name = new int[n + 1];
        onStack = new boolean[n + 1];
        parent = new int[n + 1];
        counter = new int[n + 1];
    }

    static void buildAnswer(Graph G) {
        List<Integer> path = new ArrayList<>();
        for (int i=0; i<=n; i++) {
            if (onStack[i]) path.add(i);
        }
        answer.add(path);
    }

    static void dfs(Graph G, int v, int start) {
        name[v] = currentName;
        onStack[v] = true;
        for (Node x: G.nodes[v].edges) {
            if (name[x.value] != currentName) {
                dfs(G, x.value, start);
            } else if (onStack[x.value]) {
                hasCycle = true;
                buildAnswer(G);
                break;
            }
        }
        onStack[v] = false;
    }

    static int[] counter;
    static void findMax(int x) {
        if (hasCycle) {
            ++cyclesCounter;
            counter[x]++;
            int start = x;
            x = parent[x];
            while (x != 0 && x != start) {
                counter[x]++;
                x = parent[x];
            }
        }
    }

    static void findCycles(Graph G) {
        for (int i=1; i<=n; i++) {
            hasCycle = false;
            dfs(G, i, i);
            hasAtLeastOneCycle |= hasCycle;
            findMax(i);
            currentName++;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] str = in.nextLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);

        init();

        Graph  G = new Graph(n);

        for (int i=0; i<m; i++) {
            G.connect(in.nextInt(), in.nextInt());
        }

        findCycles(G);

        if (answer.isEmpty()) {
            System.out.println("NIE");
        } else {
            for (int i=1; i<answer.size(); i++) {
                answer.get(0).retainAll(answer.get(i));
            }
            int size = answer.get(0).size();
            System.out.println(size);
            if (size > 0) {
                String format = answer.get(0).toString().replaceAll(",", "");
                format = format.substring(1, format.length() - 1);
                System.out.println(format);
            } else {
                System.out.println();
            }
        }
    }
}