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
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

public class kon{


	public Set<Integer> dfs(Map<Integer, List<Integer>> graph, int number_of_nodes) {

		Stack<Integer> stack = new Stack<Integer>();

		Set<Integer> presentInEveryCycle = null;
		boolean visited[] = new boolean[number_of_nodes + 1];
		int source = 1;
		int element = source;
		int destination = source;		

		visited[source] = true;
		stack.push(source);
		while (!stack.isEmpty()) {

			element = stack.peek();
			while (destination <= number_of_nodes) {
				boolean adjacent = graph.get(element) != null && graph.get(element).contains(destination);
				if (adjacent && visited[destination]){
					if (stack.contains(destination)) {
						Enumeration<Integer> en = stack.elements();
						Set<Integer> cycle = new TreeSet<>();
						boolean destinationFound = false;
						while (en.hasMoreElements()) {
							int el = en.nextElement();
							if (destinationFound) {
								cycle.add(el);
							} else if (el == destination) {
								cycle.add(el);
								destinationFound = true;
							}
						}

						if (presentInEveryCycle == null) {
							presentInEveryCycle = new TreeSet<>(cycle);
						} else {
							presentInEveryCycle.retainAll(cycle);
						}
					}
				} else if (adjacent && !visited[destination]) {
					stack.push(destination);
					visited[destination] = true;
					element = destination;
					destination = 1;
					continue;
				}
				destination++;
			}
			stack.pop();
		}
		return presentInEveryCycle;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n_nodes = scanner.nextInt();
		int m_edges = scanner.nextInt();

		Map<Integer, List<Integer>> graph = new HashMap<>();

		for (int i = 0; i < m_edges; i++) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			List<Integer> l = graph.get(a);
			if (l == null) {
				l = new ArrayList<>();
				graph.put(a, l);
			}
			l.add(b);
		}

		scanner.close();
		kon checkCycle = new kon();
		Set<Integer> s = checkCycle.dfs(graph, n_nodes);
		if (s == null) {
			System.out.println("NIE");
		} else {
			int size = s.size();
			System.out.println(size);
			if (size > 0) {
				StringBuilder sb = new StringBuilder();
				for (int x : s) {
					sb.append(x);
					sb.append(" ");
				}
				System.out.println(sb.substring(0, sb.length() - 1));
			}
		}
	}

}