Decompiled Hopcroft-Karp

// InputReader.java
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import kotlin.Metadata;
import kotlin.jvm.internal.IntCompanionObject;
import kotlin.jvm.internal.Intrinsics;
import org.jetbrains.annotations.NotNull;

@Metadata(
   mv = {1, 1, 1},
   bv = {1, 0, 0},
   k = 1,
   d1 = {"\u0000\u0018\n\u0002\u0018\u0002\n\u0002\u0018\u0002\n\u0000\n\u0002\u0018\u0002\n\u0002\b\u0002\n\u0002\u0010\b\n\u0000\u0018\u00002\u00020\u0001B\r\u0012\u0006\u0010\u0002\u001a\u00020\u0003¢\u0006\u0002\u0010\u0004J\u0006\u0010\u0005\u001a\u00020\u0006¨\u0006\u0007"},
   d2 = {"LInputReader;", "Ljava/io/BufferedReader;", "inputStream", "Ljava/io/InputStream;", "(Ljava/io/InputStream;)V", "nextInt", "", "production sources for module kotlin"}
)
public final class InputReader extends BufferedReader {
   public final int nextInt() {
      int c;
      for(c = this.read(); c >= 0 && c <= 32; c = this.read()) {
         ;
      }

      if(c < 0) {
         return IntCompanionObject.MIN_VALUE;
      } else {
         boolean neg = (char)c == 45;
         if(neg) {
            c = this.read();
         }

         int x;
         for(x = 0; c > 32; c = this.read()) {
            x = x * 10 + c - 48;
         }

         return x;
      }
   }

   public InputReader(@NotNull InputStream inputStream) {
      Intrinsics.checkParameterIsNotNull(inputStream, "inputStream");
      super((Reader)(new InputStreamReader(inputStream)));
   }
}
// AKt.java
import java.io.InputStream;
import kotlin.Metadata;
import kotlin.jvm.internal.IntCompanionObject;
import kotlin.jvm.internal.Intrinsics;
import org.jetbrains.annotations.NotNull;

@Metadata(
   mv = {1, 1, 1},
   bv = {1, 0, 0},
   k = 2,
   d1 = {"\u0000\u001c\n\u0000\n\u0002\u0018\u0002\n\u0002\b\u0003\n\u0002\u0010\u0002\n\u0000\n\u0002\u0010\u0011\n\u0002\u0010\u000e\n\u0002\b\u0002\u001a\u0019\u0010\u0004\u001a\u00020\u00052\f\u0010\u0006\u001a\b\u0012\u0004\u0012\u00020\b0\u0007¢\u0006\u0002\u0010\t\"\u0011\u0010\u0000\u001a\u00020\u0001¢\u0006\b\n\u0000\u001a\u0004\b\u0002\u0010\u0003¨\u0006\n"},
   d2 = {"input", "LInputReader;", "getInput", "()LInputReader;", "main", "", "args", "", "", "([Ljava/lang/String;)V", "production sources for module kotlin"}
)
public final class AKt {
   @NotNull
   private static final InputReader input;

   public static final void main(@NotNull String[] args) {
      Intrinsics.checkParameterIsNotNull(args, "args");

      while(true) {
         int n1 = input.nextInt();
         if(n1 == IntCompanionObject.MIN_VALUE) {
            return;
         }

         int n2 = input.nextInt();
         int m = input.nextInt();
         int[] from = new int[m];
         int[] to = new int[m];
         int g = 0;
         int ans = from.length - 1;
         if(g <= ans) {
            while(true) {
               to[g] = input.nextInt() - 1;
               from[g] = input.nextInt() - 1;
               if(g == ans) {
                  break;
               }

               ++g;
            }
         }

         Matching var11 = new Matching(n2, n1, from, to);
         int[] var12 = var11.getMatching();
         int i = var12.length;
         System.out.println(i);

         for(int var9 = 0; var9 < var12.length; ++var9) {
            i = var12[var9];
            String var10 = i + 1 + " ";
            System.out.print(var10);
         }

         System.out.println();
      }
   }

   @NotNull
   public static final InputReader getInput() {
      return input;
   }

   static {
      InputStream var10002 = System.in;
      Intrinsics.checkExpressionValueIsNotNull(System.in, "System.`in`");
      input = new InputReader(var10002);
   }
}
// Matching.java
import java.util.Arrays;
import kotlin.Metadata;
import kotlin.collections.ArraysKt;
import kotlin.jvm.internal.IntCompanionObject;
import kotlin.jvm.internal.Intrinsics;
import org.jetbrains.annotations.NotNull;

@Metadata(
   mv = {1, 1, 1},
   bv = {1, 0, 0},
   k = 1,
   d1 = {"\u0000\"\n\u0002\u0018\u0002\n\u0002\u0010\u0000\n\u0000\n\u0002\u0010\b\n\u0002\b\u0002\n\u0002\u0010\u0015\n\u0002\b\u0016\n\u0002\u0010\u000b\n\u0002\b\u0004\u0018\u00002\u00020\u0001B%\u0012\u0006\u0010\u0002\u001a\u00020\u0003\u0012\u0006\u0010\u0004\u001a\u00020\u0003\u0012\u0006\u0010\u0005\u001a\u00020\u0006\u0012\u0006\u0010\u0007\u001a\u00020\u0006¢\u0006\u0002\u0010\bJ\u0006\u0010\u001c\u001a\u00020\u001dJ\u000e\u0010\u001e\u001a\u00020\u001d2\u0006\u0010\u001f\u001a\u00020\u0003J\u0006\u0010 \u001a\u00020\u0006R\u0011\u0010\t\u001a\u00020\u0006¢\u0006\b\n\u0000\u001a\u0004\b\n\u0010\u000bR\u0011\u0010\f\u001a\u00020\u0006¢\u0006\b\n\u0000\u001a\u0004\b\r\u0010\u000bR\u0011\u0010\u0005\u001a\u00020\u0006¢\u0006\b\n\u0000\u001a\u0004\b\u000e\u0010\u000bR\u0011\u0010\u000f\u001a\u00020\u0006¢\u0006\b\n\u0000\u001a\u0004\b\u0010\u0010\u000bR\u0011\u0010\u0002\u001a\u00020\u0003¢\u0006\b\n\u0000\u001a\u0004\b\u0011\u0010\u0012R\u0011\u0010\u0013\u001a\u00020\u0006¢\u0006\b\n\u0000\u001a\u0004\b\u0014\u0010\u000bR\u0011\u0010\u0015\u001a\u00020\u0006¢\u0006\b\n\u0000\u001a\u0004\b\u0016\u0010\u000bR\u0011\u0010\u0017\u001a\u00020\u0006¢\u0006\b\n\u0000\u001a\u0004\b\u0018\u0010\u000bR\u0011\u0010\u0019\u001a\u00020\u0006¢\u0006\b\n\u0000\u001a\u0004\b\u001a\u0010\u000bR\u0011\u0010\u0007\u001a\u00020\u0006¢\u0006\b\n\u0000\u001a\u0004\b\u001b\u0010\u000b¨\u0006!"},
   d2 = {"LMatching;", "", "n1", "", "n2", "from", "", "to", "(II[I[I)V", "cur", "getCur", "()[I", "d", "getD", "getFrom", "he", "getHe", "getN1", "()I", "next", "getNext", "p1", "getP1", "p2", "getP2", "q", "getQ", "getTo", "bfs", "", "dfs", "v", "getMatching", "production sources for module kotlin"}
)
public final class Matching {
   @NotNull
   private final int[] he;
   @NotNull
   private final int[] next;
   @NotNull
   private final int[] cur;
   @NotNull
   private final int[] p1;
   @NotNull
   private final int[] p2;
   @NotNull
   private final int[] q;
   @NotNull
   private final int[] d;
   private final int n1;
   @NotNull
   private final int[] from;
   @NotNull
   private final int[] to;

   @NotNull
   public final int[] getHe() {
      return this.he;
   }

   @NotNull
   public final int[] getNext() {
      return this.next;
   }

   @NotNull
   public final int[] getCur() {
      return this.cur;
   }

   @NotNull
   public final int[] getP1() {
      return this.p1;
   }

   @NotNull
   public final int[] getP2() {
      return this.p2;
   }

   @NotNull
   public final int[] getQ() {
      return this.q;
   }

   @NotNull
   public final int[] getD() {
      return this.d;
   }

   public final boolean bfs() {
      int head = 0;
      int tail = 0;
      ArraysKt.fill$default(this.d, IntCompanionObject.MAX_VALUE, 0, 0, 6, (Object)null);
      int v = 0;
      int e = this.p1.length - 1;
      if(v <= e) {
         while(true) {
            if(this.p1[v] < 0) {
               this.q[tail++] = v;
               this.d[v] = 0;
            }

            if(v == e) {
               break;
            }

            ++v;
         }
      }

      while(head < tail) {
         v = this.q[head++];

         for(e = this.he[v]; e >= 0; e = this.next[e]) {
            int u = this.p2[this.to[e]];
            if(u < 0) {
               return true;
            }

            if(this.d[u] == IntCompanionObject.MAX_VALUE) {
               this.q[tail++] = u;
               this.d[u] = this.d[v] + 1;
            }
         }
      }

      return false;
   }

   public final boolean dfs(int v) {
      while(this.cur[v] >= 0) {
         int e = this.cur[v];
         int u = this.to[e];
         int w = this.p2[u];
         if(w < 0 || this.d[w] == this.d[v] + 1 && this.dfs(w)) {
            this.p1[v] = u;
            this.p2[u] = v;
            return true;
         }

         this.cur[v] = this.next[e];
      }

      return false;
   }

   @NotNull
   public final int[] getMatching() {
      int ans = 0;
      int cn = this.from.length - 1;
      if(ans <= cn) {
         while(true) {
            if(this.p1[this.from[ans]] < 0 && this.p2[this.to[ans]] < 0) {
               this.p1[this.from[ans]] = this.to[ans];
               this.p2[this.to[ans]] = this.from[ans];
            }

            if(ans == cn) {
               break;
            }

            ++ans;
         }
      }

      while(true) {
         do {
            if(!this.bfs()) {
               int[] var5 = new int[this.n1];
               cn = 0;
               int v = 0;
               int var4 = this.d.length - 1;
               if(v <= var4) {
                  while(true) {
                     if(this.d[v] != IntCompanionObject.MAX_VALUE) {
                        var5[cn++] = v;
                     }

                     if(v == var4) {
                        break;
                     }

                     ++v;
                  }
               }

               int[] var10000 = Arrays.copyOf(var5, cn);
               Intrinsics.checkExpressionValueIsNotNull(var10000, "Arrays.copyOf(this, newSize)");
               return var10000;
            }

            ans = 0;
            cn = this.cur.length - 1;
            if(ans <= cn) {
               while(true) {
                  this.cur[ans] = this.he[ans];
                  if(ans == cn) {
                     break;
                  }

                  ++ans;
               }
            }

            ans = 0;
            cn = this.q.length - 1;
         } while(ans > cn);

         while(this.d[this.q[ans]] == 0) {
            this.dfs(this.q[ans]);
            if(ans == cn) {
               break;
            }

            ++ans;
         }
      }
   }

   public final int getN1() {
      return this.n1;
   }

   @NotNull
   public final int[] getFrom() {
      return this.from;
   }

   @NotNull
   public final int[] getTo() {
      return this.to;
   }

   public Matching(int n1, int n2, @NotNull int[] from, @NotNull int[] to) {
      Intrinsics.checkParameterIsNotNull(from, "from");
      Intrinsics.checkParameterIsNotNull(to, "to");
      super();
      this.n1 = n1;
      this.from = from;
      this.to = to;
      int i = this.n1;
      int[] i$iv = new int[i];
      int i$iv1 = 0;
      int it = i - 1;
      byte var15;
      if(i$iv1 <= it) {
         while(true) {
            var15 = -1;
            i$iv[i$iv1] = var15;
            if(i$iv1 == it) {
               break;
            }

            ++i$iv1;
         }
      }

      this.he = i$iv;
      this.next = new int[this.from.length];
      this.cur = new int[this.n1];
      i = this.n1;
      i$iv = new int[i];
      i$iv1 = 0;
      it = i - 1;
      if(i$iv1 <= it) {
         while(true) {
            var15 = -1;
            i$iv[i$iv1] = var15;
            if(i$iv1 == it) {
               break;
            }

            ++i$iv1;
         }
      }

      this.p1 = i$iv;
      int[] var16 = new int[n2];
      int var17 = 0;
      i$iv1 = n2 - 1;
      if(var17 <= i$iv1) {
         while(true) {
            var15 = -1;
            var16[var17] = var15;
            if(var17 == i$iv1) {
               break;
            }

            ++var17;
         }
      }

      this.p2 = var16;
      this.q = new int[this.n1];
      this.d = new int[this.n1];
      i = 0;
      var17 = this.from.length - 1;
      if(i <= var17) {
         while(true) {
            this.next[i] = this.he[this.from[i]];
            this.he[this.from[i]] = i;
            if(i == var17) {
               break;
            }

            ++i;
         }
      }

   }
}