import java.util.*;

public class Tanssiaiset {

    public int n;
    public int m;
    public int onkoVierailtu;
    public int[][] verkkoJälkeen;
    public int[][] verkkoEnnen;
    ArrayList<Integer> polut;

    public Tanssiaiset(int n, int m) {
        this.n = n;
        this.m = m;
        verkkoJälkeen = new int[n + 2][m + 2];
        verkkoEnnen = new int[n + 2][m + 2];
        onkoVierailtu = 1;
        polut = new ArrayList<>();
    }

    public void lisaaPari(int a, int b) {
        verkkoJälkeen[a][b] += 1;
        verkkoJälkeen[0][a] += 1;
        verkkoJälkeen[b][n + 1] += 1;

        verkkoEnnen[a][b] += 1;
        verkkoEnnen[0][a] += 1;
        verkkoEnnen[b][n + 1] += 1;

    }

    public int syvyyshaku(int[][] verkko, int[] vierailtu, int s, int t, int virta) {
        if (s == t) {
            //System.out.println("Päästiin maaliin! Virta: " + virta);
            return virta;
        }

        int[] kaarenKapasiteetti = verkko[s];
        //System.out.println(Arrays.toString(kaarenKapasiteetti));
        vierailtu[s] = onkoVierailtu;

        for (int i = 0; i < kaarenKapasiteetti.length; i++) {
            if (vierailtu[i] != onkoVierailtu && kaarenKapasiteetti[i] > 0) {

                if (kaarenKapasiteetti[i] < virta) {
                    virta = kaarenKapasiteetti[i];
                }

                int virranMaara = syvyyshaku(verkko, vierailtu, i, t, virta);
                //System.out.println("Virtaa: " + virranMaara);

                if (virranMaara > 0) {
                    verkko[s][i] -= virranMaara;
                    verkko[i][s] += virranMaara;
                    //System.out.println("Päivitetään: ");
                    //System.out.println(verkko[s][i]);
                    //System.out.println(verkko[i][s]);
                    polut.add(virranMaara);
                    return virranMaara;
                }
            }
        }
        return 0;
    }

    public int laske() {
        int[] vierailtu = new int[n * m + 2];
        int maksimivirtaus = 0;

        while (true) {
            int virranMaara = syvyyshaku(verkkoJälkeen, vierailtu, 0, (n + 1), 99999999);
            onkoVierailtu++;
            //System.out.println(onkoVierailtu);
            maksimivirtaus += virranMaara;

            if (virranMaara == 0) {
                return maksimivirtaus;
            }
        }
    }

    public ArrayList<Pari> muodosta() {
        int maksimivirtaus = laske();
        System.out.println(maksimivirtaus);

        System.out.println("Verkko ennen");
        System.out.println(Arrays.deepToString(verkkoEnnen).replace("], ", "]\n").replace("[[", "[").replace("]]", "]"));
        System.out.println("_________");
        System.out.println("Verkko jälkeen");
        System.out.println(Arrays.deepToString(verkkoJälkeen).replace("], ", "]\n").replace("[[", "[").replace("]]", "]"));

        return new ArrayList<>();
    }

}

public class Pari {
    int opiskelija1; // Kumpulan opiskelija
    int opiskelija2; // Viikin opiskelija

    public Pari(int a, int b) {
        opiskelija1 = a;
        opiskelija2 = b;
    }

    public String toString() {
        return "("+opiskelija1+","+opiskelija2+")";
    }
}