// Solution attempt at NAIPC 2019 // Trains, Planes, and No Automobiles // // @author godmar import java.util.*; import java.util.stream.*; import java.io.*; public class TrainsPlanesNoAutos_godmar { public static void main(String ...av) { Scanner s = new Scanner(); int n = s.nextInt(); int m = s.nextInt(); Edge [] edges = new Edge[m]; HopcroftKarp hk = new HopcroftKarp(n, n); for (int i = 0; i < m; i++) { int a = s.nextInt() - 1; int b = s.nextInt() - 1; edges[i] = new Edge(a, b); hk.addEdge(a, b); } int msz = hk.findMaxMatching(); int unmatched = 0; boolean [] hasSuccessor = new boolean[n]; ArrayList airports = new ArrayList<>(); for (int u = 0; u < n; u++) { if (hk.matching[u] != -1) { // System.err.printf("edge %d -> %d is included%n", hk.matching[u]+1, u+1); hasSuccessor[hk.matching[u]] = true; continue; } unmatched++; airports.add(u); } for (int u = 0; u < n; u++) if (!hasSuccessor[u]) airports.add(u); System.out.println(unmatched - 1); if (unmatched != 1) { String answer = airports.stream().map(x -> x + 1).distinct().sorted() .map(Object::toString).collect(Collectors.joining(" ")); System.out.println(answer); } } static class Edge { int u, v; Edge(int u, int v) { this.u = u; this.v = v; } } /** * O(E * sqrt(V)) * Bipartite Matching * Ported by cjwu from * https://sites.google.com/site/indy256/algo_cpp/hopcroft_karp */ static class HopcroftKarp { int n1, n2; int edges = 0; int[] last; List prev; List head; int[] matching; int[] dist; int[] Q; boolean[] used; boolean[] vis; public HopcroftKarp(int n1, int n2) { this.n1 = n1; this.n2 = n2; last = new int[n1]; prev = new ArrayList<>(); head = new ArrayList<>(); matching = new int[n2]; dist = new int[n1]; Q = new int[n1]; used = new boolean[n1]; vis = new boolean[n1]; Arrays.fill(last, -1); } public void addEdge(int u, int v) { head.add(v); prev.add(last[u]); last[u] = edges++; } private void bfs() { Arrays.fill(dist, -1); int sizeQ = 0; for (int u = 0; u < n1; u++) { if (!used[u]) { Q[sizeQ++] = u; dist[u] = 0; } } for (int i = 0; i < sizeQ; i++) { int u1 = Q[i]; for (int e = last[u1]; e >= 0; e = prev.get(e)) { int u2 = matching[head.get(e)]; if (u2 >= 0 && dist[u2] < 0) { dist[u2] = dist[u1] + 1; Q[sizeQ++] = u2; } } } } private boolean dfs(int u1) { vis[u1] = true; for (int e = last[u1]; e >= 0; e = prev.get(e)) { int v = head.get(e); int u2 = matching[v]; if (u2 < 0 || !vis[u2] && dist[u2] == dist[u1] + 1 && dfs(u2)) { matching[v] = u1; used[u1] = true; return true; } } return false; } public int findMaxMatching() { Arrays.fill(matching, -1); int numMatches = 0; int f; do { bfs(); Arrays.fill(vis, false); f = 0; for (int u = 0; u < n1; u++) { if (!used[u] && dfs(u)) { f++; } } numMatches += f; } while (f > 0); return numMatches; } } //-----------Scanner class for faster input---------- /* Provides similar API as java.util.Scanner but does not * use regular expression engine. */ public static class Scanner { BufferedReader br; StringTokenizer st; public Scanner(Reader in) { br = new BufferedReader(in); } public Scanner() { this(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } // Slightly different from java.util.Scanner.nextLine(), // which returns any remaining characters in current line, // if any. String readNextLine() { String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } int[] readIntArray(int n) { int[] a = new int[n]; for (int idx = 0; idx < n; idx++) { a[idx] = nextInt(); } return a; } long[] readLongArray(int n) { long[] a = new long[n]; for (int idx = 0; idx < n; idx++) { a[idx] = nextLong(); } return a; } } //-------------------------------------------------------- }