#include <deque>
#include <climits>
#include <iostream>
#include <utility>
#include <vector>

struct grafica_flujo {
   std::vector<std::vector<int>> listas;
   std::vector<std::vector<int>> capacidad;
   int fuente, sumidero;

   grafica_flujo(int n, int f, int s)
   : listas(n), capacidad(n, std::vector<int>(n, 0)), fuente(f), sumidero(s) {
   }

   void agrega_arco(int v1, int v2, int c) {
      listas[v1].push_back(v2);
      listas[v2].push_back(v1);
      capacidad[v1][v2] = c;
   }

   int flujo_maximo( ) {
      int res = 0;
      for (;;) {
         auto [flujo, camino] = aumenta_flujo( );
         if (flujo == 0) {
            return res;
         }
         res += flujo;
         for (auto [v1, v2] : camino) {
            capacidad[v1][v2] -= flujo;
            capacidad[v2][v1] += flujo;
         }
      }
   }

   std::pair<int, std::vector<std::pair<int, int>>> aumenta_flujo( ) {
      std::deque<int> cola = { fuente };
      std::vector<int> distancia(listas.size( ), -1), previo(listas.size( ), -1);
      distancia[fuente] = 0;
      previo[fuente] = fuente;
      do {
         int procesar = cola.front( );
         cola.pop_front( );
         for (int v : listas[procesar]) {
            if (distancia[v] == -1 && capacidad[procesar][v] > 0) {
               distancia[v] = distancia[procesar] + 1;
               previo[v] = procesar;
               cola.push_back(v);
            }
         }
      } while (!cola.empty( ));

      if (distancia[sumidero] == -1) {
         return { 0, { } };
      } else {
         std::vector<std::pair<int, int>> camino;
         int flujo = INT_MAX, actual = sumidero;
         do {
            int anterior = previo[actual];
            camino.push_back({ anterior, actual });
            flujo = std::min(flujo, capacidad[anterior][actual]);
            actual = anterior;
         } while (actual != fuente);
         return { flujo, camino };
      }
   }
};

int main( ) {
   grafica_flujo g(5, 3, 4);     // número de vértices, id de la fuente, id del sumidero
   g.agrega_arco(3, 0, 1);       // vértice de origen, vértice de destino, capacidad del arco
   g.agrega_arco(3, 1, 1);
   g.agrega_arco(0, 2, 1);       // en el último ejemplo que dibujé y que quise correr en clase antes de irnos, por error puse 3, 2, 1 aquí
   g.agrega_arco(1, 2, 1);
   g.agrega_arco(2, 4, 1);

   std::cout << g.flujo_maximo( ) << "\n";
   for (auto [v1, v2] : { std::pair(3, 0), std::pair(3, 1), std::pair(0, 2), std::pair(1, 2), std::pair(2, 4) }) {      // ejemplo para ver por dónde se mandó el flujo
      std::cout << v1 << " " << v2 << ": " << g.capacidad[v2][v1] << "\n";
   }
}