import java.util.*;

public class Maksimivirtaus {
    public static final int KOKO = 6;
    public static int[][] verkko = new int[KOKO+1][KOKO+1];
    public static int alku = 1;
    public static int loppu = 6;
    public static int virtaus = 0;

    public static class JononSolmu {
        public int tunnus;
        public JononSolmu vanha;

        public JononSolmu(int tunnus, JononSolmu vanha) {
            this.tunnus = tunnus;
            this.vanha = vanha;
        }
    }

    public static LinkedList<Integer> reitti;
    public static TreeSet<Integer> mukana;
    public static LinkedList<JononSolmu> jono;
    public static int lisays;

    public static void etsiReitti() {
        jono.addLast(new JononSolmu(alku, null));
        while (jono.size() > 0) {
            JononSolmu solmu = jono.removeFirst();
            if (solmu.tunnus == loppu) {
                lisays = verkko[solmu.vanha.tunnus][solmu.tunnus];
                while (true) {
                    reitti.addFirst(solmu.tunnus);
                    if (solmu.vanha == null) break;
                    lisays = Math.min(lisays, verkko[solmu.vanha.tunnus][solmu.tunnus]);
                    solmu = solmu.vanha;
                }
                return;
            }
            for (int uusi = 1; uusi <= KOKO; uusi++) {
                if (verkko[solmu.tunnus][uusi] > 0 && !mukana.contains(uusi)) {
                    mukana.add(uusi);
                    jono.addLast(new JononSolmu(uusi, solmu));
                }
            }
        }
    }

    public static void main(String[] args) {
        verkko[1][2] = 5;
        verkko[1][3] = 3;
        verkko[2][4] = 6;
        verkko[3][2] = 3;
        verkko[3][5] = 1;
        verkko[4][5] = 8;
        verkko[4][6] = 5;
        verkko[5][6] = 2;
        while (true) {
            reitti = new LinkedList<Integer>();
            mukana = new TreeSet<Integer>();
            jono = new LinkedList<JononSolmu>();
            lisays = 0;
            etsiReitti();
            if (lisays == 0) break;
            System.out.println("Reitti: " + reitti);
            System.out.println("Lisäys: " + lisays);
            virtaus += lisays;
            for (int i = 0; i < reitti.size()-1; i++) {
                verkko[reitti.get(i)][reitti.get(i+1)] -= lisays;
                verkko[reitti.get(i+1)][reitti.get(i)] += lisays;
            }
        }
        System.out.println("Maksimivirtaus: " + virtaus);
    }
}