// 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_godmar2 { @SuppressWarnings("unchecked") public static void main(String ...av) { Scanner s = new Scanner(); int n = s.nextInt(); List [] rev = new List[n]; // reverse graph Integer [] nodes = new Integer[n]; for (int i = 0; i < n; i++) { rev[i] = new ArrayList<>(); nodes[i] = i; } 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); rev[b].add(nodes[a]); hk.addEdge(a, b); } int msz = hk.findMaxMatching(); int unmatched = 0; boolean [] couldBeAirport = new boolean[n]; for (int u = 0; u < n; u++) { if (!hk.used[u]) { couldBeAirport[u] = true; unmatched++; //System.err.printf("no successor for node %d%n", u+1); } if (hk.matching[u] == -1) { //System.err.printf("no predecessor for node %d%n", u+1); couldBeAirport[u] = true; } } // can we rewire any matches without losing maximality? for (int v = 0; v < n; v++) { if (hk.matching[v] != -1) { // System.err.printf("consider matching edge %d -> %d%n", hk.matching[v]+1, v+1); for (int u : rev[v]) { if (!hk.used[u]) { //System.err.printf("could have %d -> %d and %d airport%n", u+1, v+1, hk.matching[v]+1); couldBeAirport[hk.matching[v]] = true; } } } } StringBuilder output = new StringBuilder(); output.append((unmatched - 1) + "\n"); if (unmatched != 1) { String sep = ""; for (int u = 0; u < n; u++) { if (couldBeAirport[u]) { output.append(sep + (u+1)); sep = " "; } } } System.out.println(output.toString()); } 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; } } //-------------------------------------------------------- }