// Maksymalny przepływ
// algorytm Edmondsa-Karpa
// Data: 08.08.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program maxflow;

// Definicja typu
// elementów listy
//----------------
type
  PSLel = ^SLel;
  SLel = record
    next  : PSLel;
    Data: integer;
  end;

// Definicja typu
// obiektowego queue
//------------------
  queue = object
    private
      head : PSLel;
      tail : PSLel;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push(v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor
//------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor
//-----------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza,
// czy kolejka jest pusta
//-----------------------
function queue.empty : boolean;
begin
  if head = nil then
    empty := true
  else
    empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then
    front := -MAXINT
  else
    front := head^.data;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(v : integer);
var
  p : PSLel;
begin
  new(p);
  p^.next := nil;
  p^.Data:= v;
  if tail = nil then
    head := p
  else
    tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PSLel;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then
      tail := nil;
    dispose(p);
  end;
end;

//---------------
// Program główny
//---------------

var
  // Kolejka
  Q : queue;
  // Macierz przepustowości
  C : array of array of integer;
  // Macierz przepływów netto
  F : array of array of integer;
  // Tablica poprzedników
  P : array of integer;
  // Tablica przepustowości
  // rezydualnych
  CFP : array of integer;
  // Zmienne proste algorytmu
  n,m,s,t,fmax,cp,x,y,i,j : integer;
  // Do wychodzenia
  // z zagnieżdżonych pętli
  esc : boolean;

begin
  // Inicjujemy kolejkę
  Q.init;
  // Ze standardowego wejścia
  // odczytujemy:
  // n - liczbę wierzchołków
  // w grafie sieci
  // m - liczbę krawędzi
  read(n, m);
  // Tworzymy dynamicznie macierze:
  // C - przepustowości krawędzi
  // F - przepływy w krawędziach
  SetLength(C, n);
  SetLength(F, n);
  for i := 0 to n-1 do
  begin
    SetLength(C[i], n);
    SetLength(F[i], n);
  end;
  // Tworzymy dynamicznie tablice:
  // P - poprzedniki na ścieżkach
  //     tworzonych przez BFS
  // CFP - przepustowość ścieżek
  SetLength(P, n);
  SetLength(CFP, n);
  // Zerujemy macierze
  // przepustowości i przepływów
  for i := 0 to n-1 do
    for j := 0 to n-1 do
    begin
      C[i][j] := 0;
      F[i][j] := 0;
    end;
  // Ze standardowego wejścia
  // odczytujemy definicje krawędzi.
  // Każda definicja składa się
  // z trzech liczb:
  // x,y - wierzchołki grafu
  //       połączone krawędzią
  // cp  - przepustowość krawędzi
  // Odczytane dane zapamiętujemy:
  // C[x][y] = cp
  for i := 1 to m do
  begin
    read(x, y, cp);
    C[x][y] := cp;
  end;
  // Na koniec odczytujemy
  // numer wierzchołka źródła s
  // oraz numer wierzchołka
  // ujścia t
  read(s, t);

  //*****************************
  //** Tutaj rozpoczyna się    **
  //** algorytm Edmondsa-Karpa **
  //*****************************

  // Rozpoczynamy od maksymalnego
  // przepływu równego zero
  fmax := 0;
  // W pętli szukamy ścieżek
  // rozszerzających dotąd,
  // dopóki istnieją w sieci
  // rezydualnej. Każda znaleziona
  // ścieżka zwiększa przepływ
  // wzdłuż zawartych w niej
  // krawędzi grafu sieci
  // przepływowej

  while true do
  begin
    // Na początku pętli
    // zerujemy tablicę
    // poprzedników P
    for i := 0 to n-1 do
      P[i] := -1;
    // źródło nie posiada
    // poprzednika. Wpisujemy
    // tutaj -2, aby BFS nie
    // wybierało źródła
    P[s] := -2;
    // Do CFP[s] wpisujemy
    // największą liczbę
    // całkowitą
    CFP[s] := MAXINT;
    // Zerujemy kolejkę
    // i umieszczamy w niej
    // źródło s
    while not Q.empty do
      Q.pop;
    Q.push(s);
    // Zmienna esc umożliwia
    // odpowiednie wychodzenie
    // z dwóch zagnieżdżonych
    // pętli - zamiast polecenia
    // goto.
    esc := false;
    // Rozpoczynamy pętlę
    // wyszukującą ścieżki BFS.
    // Pętla kończy się
    // w przypadku braku
    // dalszych wierzchołków
    // w kolejce
    while not Q.empty do
    begin
      // Z początku kolejki
      // pobieramy element
      // i usuwamy go z kolejki
      x := Q.front; Q.pop;
      // Sprawdzamy wszystkich
      // sąsiadów wierzchołka x
      // przeglądając wiersz
      // macierzy C
      for y := 0 to n-1 do
      begin
        // Dla sąsiada y
        // wyznaczamy przepustowość
        // rezydualną krawędzi x->y.
        // Jeśli krawędź nie
        // istnieje w sieci,
        // to otrzymamy w cp wynik
        // zero
        cp := C[x][y]-F[x][y];
        // Sprawdzamy, czy krawędź
        // istnieje oraz czy
        // wierzchołek y nie był
        // już wcześniej wybrany
        // przez BFS. W takim
        // przypadku P[y] ma wartość
        // różną od -1.
        if (cp <> 0) and
           (P[y] = -1) then
        begin
          // W P[y] zapamiętujemy,
          // iż poprzednikiem y
          // jest x
          P[y] := x;
          // Dla wierzchołka y
          // obliczamy dotychczasową
          // przepustowość rezydualną
          // ścieżki. Jest to mniejsza
          // wartość z przepustowości
          // ścieżki dla poprzednika x
          // i bieżącej przepustowości
          // rezydualnej krawędzi
          // x->y.
          if CFP[x] > cp then
            CFP[y] := cp
          else
            CFP[y] := CFP[x];
          // Jeśli osiągnęliśmy
          // ujście, to ścieżka
          // jest kompletna
          if y = t then
          begin
            // Zwiększamy przepływ
            // maksymalny
            // o przepustowość
            // rezydualną ścieżki -
            // wykorzystujemy tablicę
            // CFP
            inc(fmax, CFP[t]);
            // Idziemy wstecz
            // po ścieżce
            // zwiększając przepływy
            // wzdłuż jej krawędzi
            // w kierunku zgodnym
            /// ze ścieżką oraz
            // zmniejszając przepływy
            // w kierunku przeciwnym
            i := y;
            while i <> s do
            begin
              x := P[i];
              inc(F[x][i], CFP[t]);
              dec(F[i][x], CFP[t]);
              i := x;
            end;
            // Ustawiamy esc na true,
            // co spowoduje wyjście
            // z obu pętli
            esc := true; break;
          end;
          // Jeśli wierzchołek y nie
          // jest ujściem t, to
          // dopisujemy go na końcu
          // kolejki Q i kontynuujemy
          // pętlę BFS
          Q.push(y);
        end;
      end;
      // Tutaj wychodzimy z pętli
      // while, jeśli została
      // znaleziona ścieżka
      //rozszerzająca
      if esc then break;
    end;
    // Jeśli nie znaleziono ścieżki
    // rozszerzającej, to esc = false
    // i w tym miejscu nastąpi wyjście
    // z głównej pętli while
    if not esc then break;
  end;
  // Prezentujemy wyniki obliczeń.
  // Najpierw wypisujemy wartość
  // maksymalnego przepływu
  writeln;
  writeln('fmax = ', fmax);
  writeln;
  // Następnie wypisujemy przepływy
  // netto wzdłuż krawędzi
  for x := 0 to n-1 do
    for y := 0 to n-1 do
      if C[x][y] <> 0 then
        writeln(x,' -> ',y,' ',
                F[x][y],':',C[x][y]);
  writeln;
  // Usuwamy zmienne dynamiczne
  for i := 0 to n-1 do
  begin
    SetLength(C[i], 0);
    SetLength(F[i], 0);
  end;
  SetLength(C, 0);
  SetLength(F, 0);
  SetLength(P, 0);
  SetLength(CFP, 0);
  Q.destroy;
end.

// Maksymalny przepływ
// Algorytm Edmondsa-Karpa
// Data: 08.08.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

// Definicja typu
// elementów listy
//----------------
struct SLel
{
  SLel * next;
  int data;
};

// Definicja typu
// obiektowego queue
//------------------
class queue
{
  private:
    SLel * head;
    SLel * tail;

  public:
    // konstruktor
    queue();
    // destruktor
    ~queue();
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor
//------------
queue::queue()
{
  head = tail = nullptr;
}

// Destruktor
//-----------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza,
// czy kolejka jest pusta
//-----------------------
bool queue::empty(void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna
// to -MAXINT
//-------------------------
int queue::front(void)
{
  if(head)
    return head->data;
  else
    return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int v)
{
  SLel * p = new SLel;
  p->next = NULL;
  p->data = v;
  if(tail)
    tail->next = p;
  else
    head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop(void)
{
  if(head)
  {
    SLel * p = head;
    head = head->next;
    if(!head) tail = nullptr;
    delete p;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  // Kolejka
  queue Q;
  // Macierz przepustowości
  int ** C;
  // Macierz przepływów netto
  int ** F;
  // Tablica poprzedników
  int * P;
  // Tablica przepustowości
  // rezydualnych
  int * CFP;
  // Zmienne proste algorytmu
  int n,m,s,t,fmax,cp,x,y,i,j;
  // Do wychodzenia
  // z zagnieżdżonych pętli
  bool esc;

  // Ze standardowego wejścia
  // odczytujemy:
  // n - liczbę wierzchołków
  //     w grafie sieci
  // m - liczbę krawędzi
  cin >> n >> m;
  // Tworzymy dynamicznie
  // macierze:
  // C - przepustowości krawędzi
  // F - przepływy w krawędziach
  C = new int * [n];
  F = new int * [n];
  for(i = 0; i < n; i++)
  {
    C[i] = new int [n];
    F[i] = new int [n];
  }

  // Tworzymy dynamicznie tablice:
  // P - poprzedniki na ścieżkach
  //     tworzonych przez BFS
  // CFP - przepustowość ścieżek
  P = new int [n];
  CFP = new int [n];
  // Zerujemy macierze przepustowości
  // i przepływów
  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
      C[i][j] = F[i][j] = 0;

  // Ze standardowego wejścia
  // odczytujemy definicje krawędzi.
  // Każda definicja składa się
  // z trzech liczb:
  // x, y - wierzchołki grafu
  //        połączone krawędzią
  // cp - przepustowość krawędzi
  // Odczytane dane zapamiętujemy:
  // C[x][y] = cp

  for(i = 0; i < m; i++)
  {
    cin >> x >> y >> cp;
    C[x][y] = cp;
  }

  // Na koniec odczytujemy numer
  // wierzchołka źródła s oraz
  // numer wierzchołka ujścia t

  cin >> s >> t;

  //*****************************
  //** Tutaj rozpoczyna się    **
  //** algorytm Edmondsa-Karpa **
  //*****************************

  // Rozpoczynamy od maksymalnego
  // przepływu równego zero
  fmax = 0;
  // W pętli szukamy ścieżek
  // rozszerzających dotąd,
  // dopóki istnieją w sieci
  // rezydualnej. Każda znaleziona
  // ścieżka zwiększa przepływ
  // wzdłuż zawartych w niej
  // krawędzi grafu sieci
  // przepływowej
  while(true)
  {
    // Na początku pętli zerujemy
    // tablicę poprzedników P
    for(i = 0; i < n; i++)
      P[i] = -1;
    // źródło nie posiada
    // poprzednika. Wpisujemy
    // tutaj -2, aby BFS nie
    // wybierało źródła
    P[s] = -2;
    // Do CFP[s] wpisujemy
    // największą liczbę
    // całkowitą
    CFP[s] = MAXINT;
    // Zerujemy kolejkę
    // i umieszczamy w niej
    // źródło s
    while(!Q.empty())
      Q.pop();
    Q.push(s);
    // Zmienna esc umożliwia
    // odpowiednie wychodzenie
    // z dwóch zagnieżdżonych
    // pętli - zamiast polecenia
    // goto.
    esc = false;
    // Rozpoczynamy pętlę
    // wyszukującą ścieżki BFS.
    // Pętla kończy się
    // w przypadku braku dalszych
    // wierzchołków w kolejce
    while(!Q.empty())
    {
      // Z początku kolejki
      // pobieramy element
      // i usuwamy go z kolejki
      x = Q.front(); Q.pop();
      // Sprawdzamy wszystkich
      // sąsiadów wierzchołka x
      // przeglądając wiersz
      // macierzy C
      for(y = 0; y < n; y++)
      {
        // Dla sąsiada y
        // wyznaczamy przepustowość
        // rezydualną krawędzi x->y.
        // Jeśli krawędź nie istnieje
        // w sieci, to otrzymamy
        // w cp wynik zero
        cp = C[x][y]-F[x][y];
        // Sprawdzamy, czy krawędź
        // istnieje oraz czy
        // wierzchołek y nie był
        // już wcześniej wybrany
        // przez BFS. W takim
        // przypadku P[y] ma wartość
        // różną od -1.
        if(cp && (P[y] == -1))
        {
          // W P[y] zapamiętujemy,
          // iż poprzednikiem y jest x
          P[y] = x;
          // Dla wierzchołka y
          // obliczamy dotychczasową
          // przepustowość rezydualną
          // ścieżki. Jest to mniejsza
          // wartość z przepustowości
          // ścieżki dla poprzednika x
          // i bieżącej przepustowości
          // rezydualnej krawędzi
          // x->y.
          CFP[y] = CFP[x] > cp
                   ? cp : CFP[x];
          // Jeśli osiągnęliśmy
          // ujście, to ścieżka jest
          // kompletna
          if(y == t)
          {
            // Zwiększamy przepływ
            // maksymalny o
            // przepustowość
            // rezydualną ścieżki
            // - wykorzystujemy
            // tablicę CFP
            fmax += CFP[t];
            // Idziemy wstecz
            // po ścieżce
            // zwiększając przepływy
            // wzdłuż jej krawędzi
            // w kierunku zgodnym
            // ze ścieżką oraz
            // zmniejszając
            // przepływy w kierunku
            // przeciwnym
            i = y;
            while(i != s)
            {
              x = P[i];
              F[x][i] += CFP[t];
              F[i][x] -= CFP[t];
              i = x;
            }
            // Ustawiamy esc na true,
            // co spowoduje wyjście
            // z obu pętli
            esc = true; break;
          }
          // Jeśli wierzchołek y
          // nie jest ujściem t,
          // to dopisujemy go na
          // końcu kolejki Q
          // i kontynuujemy pętlę BFS
          Q.push(y);
        }
      }
      // Tutaj wychodzimy z pętli
      // while, jeśli została
      // znaleziona ścieżka
      // rozszerzająca
       if(esc) break;
    }
    // Jeśli nie znaleziono ścieżki
    // rozszerzającej, to esc = false
    // i w tym miejscu nastąpi wyjście
    // z głównej pętli while
    if(!esc) break;
  }
  // Prezentujemy wyniki obliczeń.
  // Najpierw wypisujemy wartość
  // maksymalnego przepływu
  cout << endl << "fmax = "
       << fmax << endl << endl;
  // Następnie wypisujemy przepływy
  // netto wzdłuż krawędzi
  for(x = 0; x < n; x++)
    for(y = 0; y < n; y++)
      if(C[x][y])
        cout << x << " -> "
             << y << " "
             << F[x][y] << ":"
             << C[x][y] << endl;
  cout << endl;
  // Usuwamy zmienne dynamiczne
  for(i = 0; i < n; i++)
  {
    delete [] C[i];
    delete [] F[i];
  }
  delete [] C;
  delete [] F;
  delete [] P;
  delete [] CFP;
  return 0;
}

' Maksymalny przepływ
' Algorytm Edmondsa-Karpa
' Data: 08.08.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

Const MAXINT = 2147483647

' Definicja typu elementów listy
'-------------------------------
Type SLel
  next As SLel Ptr
  data As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As SLel Ptr
    tail As SLel Ptr

  Public:
    Declare Constructor
    Declare Destructor
    Declare Function empty As Integer
    Declare Function front As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor
'------------
Constructor queue
  head = 0
  tail = 0
End Constructor

' Destruktor
'-----------
Destructor queue
  While empty = 0
    pop
  Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->data
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal v As Integer)
  Dim p As SLel Ptr
  p = new SLel
  p->next = 0
  p->data = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop
  Dim p As SLel Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

'---------------
' Program główny
'---------------

' Kolejka
Dim As queue Q
' Macierz przepustowości
Dim As Integer Ptr Ptr C
' Macierz przepływów netto
Dim As Integer Ptr Ptr F
' Tablica poprzedników
Dim As Integer Ptr P
' Tablica przepustowości rezydualnych
Dim As Integer Ptr CFP
' Zmienne proste algorytmu
Dim As Integer n,m,s,t,fmax,cp,x,y,i,j
' Do wychodzenia z zagnieżdżonych
' pętli
Dim As Byte esc

Open Cons For Input As #1
' Ze standardowego wejścia odczytujemy
' n-liczbę wierzchołków w grafie sieci
' m-liczbę krawędzi
Input #1, n, m
' Tworzymy dynamicznie macierze:
' C - przepustowości krawędzi
' F - przepływy w krawędziach
C = New Integer Ptr [n]
F = New Integer Ptr [n]
For i = 0 To n-1
  C[i] = New Integer [n]
  F[i] = New Integer [n]
Next
' Tworzymy dynamicznie tablice:
' P  - poprzedniki na ścieżkach
'      tworzonych przez BFS
' CFP - przepustowość ścieżek
P = New Integer [n]
CFP = New Integer [n]
' Zerujemy macierze przepustowości
' i przepływów
For i = 0 To n-1
  For j = 0 To n-1
  	 C[i][j] = 0
  	 F[i][j] = 0
  Next
Next
' Ze standardowego wejścia odczytujemy
' definicje krawędzi. Każda definicja
' składa się z trzech liczb:
' x, y - wierzchołki grafu połączone
'        krawędzią
' cp - przepustowość krawędzi
' Odczytane dane zapamiętujemy:
' C[x][y] = cp
For i = 1 To m
  Input #1, x, y, cp
  C[x][y] = cp
Next
' Na koniec odczytujemy numer
' wierzchołka źródła s oraz numer
' wierzchołka ujścia t
Input #1, s, t
Close #1

'*****************************
'** Tutaj rozpoczyna się    **
'** algorytm Edmondsa-Karpa **
'*****************************

' Rozpoczynamy od maksymalnego
' przepływu równego zero
fmax = 0
' W pętli szukamy ścieżek
' rozszerzających dotąd, dopóki
' istnieją w sieci rezydualnej.
' Każda znaleziona ścieżka zwiększa
' przepływ wzdłuż zawartych w niej
' krawędzi grafu sieci przepływowej
While 1
  ' Na początku pętli zerujemy
  ' tablicę poprzedników P
  For i = 0 To n-1
    P[i] = -1
  Next
  ' źródło nie posiada poprzednika.
  ' Wpisujemy tutaj -2, aby BFS nie
  ' wybierało źródła
  P[s] = -2
  ' Do CFP[s] wpisujemy największą
  ' liczbę całkowitą
  CFP[s] = MAXINT
  ' Zerujemy kolejkę i umieszczamy
  ' w niej źródło s
  While Q.empty = 0
    Q.pop
  Wend
  Q.push(s)
  ' Zmienna esc umożliwia odpowiednie
  ' wychodzenie z dwóch zagnieżdżonych
  ' pętli - zamiast polecenia goto.
  esc = 0
  ' Rozpoczynamy pętlę wyszukującą
  ' ścieżki BFS. Pętla kończy się
  ' w przypadku braku dalszych
  ' wierzchołków w kolejce
  While Q.empty = 0
    ' Z początku kolejki pobieramy
    ' element i usuwamy go z kolejki
    x = Q.front
    Q.pop
    ' Sprawdzamy wszystkich sąsiadów
    ' wierzchołka x przeglądając
    ' wiersz macierzy C
    For y = 0 To n-1
      ' Dla sąsiada y wyznaczamy
      ' przepustowość rezydualną
      ' krawędzi x->y. Jeśli krawędź
      ' nie istnieje w sieci, to
      ' otrzymamy w cp wynik zero
      cp = C[x][y]-F[x][y]
      ' Sprawdzamy, czy krawędź
      ' istnieje oraz czy wierzchołek
      ' y nie był już wcześniej
      ' wybrany przez BFS. W takim
      ' przypadku P[y] ma wartość
      ' różną od -1.
      If cp <> 0 AndAlso P[y] = -1 Then
        ' W P[y] zapamiętujemy, iż
        ' poprzednikiem y jest x
        P[y] = x
        ' Dla wierzchołka y obliczamy
        ' dotychczasową przepustowość
        ' rezydualną ścieżki. Jest to
        ' mniejsza wartość
        ' z przepustowości ścieżki dla
        ' poprzednika x i bieżącej
        ' przepustowości rezydualnej
        ' krawędzi x->y.
        If CFP[x] > cp Then
          CFP[y] = cp
        Else
          CFP[y] = CFP[x]
        EndIf
        ' Jeśli osiągnęliśmy ujście,
        ' to ścieżka jest kompletna
        If y = t Then
          ' Zwiększamy przepływ
          ' maksymalny o przepustowość
          ' rezydualną ścieżki -
          ' wykorzystujemy tablicę CFP
          fmax += CFP[t]
          ' Idziemy wstecz po ścieżce
          ' zwiększając przepływy
          ' wzdłuż jej krawędzi
          ' w kierunku zgodnym ze
          ' ścieżką oraz zmniejszając
          ' przepływy w kierunku
          ' przeciwnym
          i = y
          While i <> s
            x = P[i]
            F[x][i] += CFP[t]
            F[i][x] -= CFP[t]
            i = x
          Wend
          ' Ustawiamy esc na true, co
          ' spowoduje wyjście z obu
          ' pętli
          esc = 1
          Exit For
        EndIf
        ' Jeśli wierzchołek y nie jest
        ' ujściem t, to dopisujemy go
        ' na końcu kolejki Q
        ' i kontynuujemy pętlę BFS
        Q.push(y)
      EndIf
    Next
    ' Tutaj wychodzimy z pętli while,
    ' jeśli została znaleziona ścieżka
    ' rozszerzająca
    If esc = 1 Then Exit While
  Wend
  ' Jeśli nie znaleziono ścieżki
  ' rozszerzającej, to esc = false
  ' i w tym miejscu nastąpi wyjście
  ' z głównej pętli while
  If esc = 0 Then Exit While
Wend
' Prezentujemy wyniki obliczeń.
' Najpierw wypisujemy wartość
' maksymalnego przepływu
Print
Print "fmax =";fmax
Print
' Następnie wypisujemy przepływy netto
' wzdłuż krawędzi
For x = 0 To n-1
  For y = 0 To n-1
    If C[x][y] <> 0 Then Print Using _
      "& -> & &:&";x;y;F[x][y];C[x][y]
  Next
Next
Print
' Usuwamy zmienne dynamiczne
for i = 0 To n-1
  Delete [] C[i]
  Delete [] F[i]
Next
Delete [] C
Delete [] F
Delete [] P
Delete [] CFP
End

# Maksymalny przepływ
# Algorytm Edmondsa-Karpa
# Data: 06.04.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

MAXINT = 2147483647

# Elementy listy
class SLel:
    def __init__(self):
        self.next = None
        self.data = 0


# Obiekt Queue
#-------------

class Queue:
    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None


    # Destruktor
    def __del__(self):
        while not self.empty():
            self.pop()


    # Kolejka jest pusta?
    def empty(self):
        return not self.head


    # Zwraca początek kolejki.
    # Wartość specjalna to -MAXINT
    def front(self):
        global MAXINT
        if not self.head:
            return -MAXINT
        else:
            return self.head.data


    # Zapisuje do kolejki
    def push(self,v):
        p = SLel()
        p.data = v
        if not self.tail:
            self.head = p
        else:
            self.tail.next = p
        self.tail = p


    # Usuwa z kolejki
    def pop(self):
        if self.head:
            self.head = self.head.next
        if not self.head:
            self.tail = None


#---------------
# Program główny
#---------------

# Kolejka
q = Queue()

# Ze standardowego wejścia odczytujemy
# n — liczbę wierzchołków w grafie sieci
# m — liczbę krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy dynamicznie macierze:
# C — przepustowości krawędzi
# F — przepływy w krawędziach
c = [[0 for j in range(n)] for i in range(n)]
f = [[0 for j in range(n)] for i in range(n)]
# Tworzymy dynamicznie tablice:
# P — poprzedniki na ścieżkach
#     tworzonych przez BFS
# CFP — przepustowość ścieżek
pp = [0] * n
cfp = [0] * n
# Ze standardowego wejścia odczytujemy
# definicje krawędzi. Każda definicja
# składa się z trzech liczb:
# x, y — wierzchołki grafu połączone
#        krawędzią
# cp   — przepustowość krawędzi
# Odczytane dane zapamiętujemy:
# C[x][y] = cp
for i in range(m):
    z = input().split()
    x = int(z[0])
    y = int(z[1])
    cp = int(z[2])
    c[x][y] = cp
# Na koniec odczytujemy numer
# wierzchołka źródła s oraz numer
# wierzchołka ujścia t
x = input().split()
s = int(x[0])
t = int(x[1])

#*****************************
#** Tutaj rozpoczyna się    **
#** algorytm Edmondsa-Karpa **
#*****************************

# Rozpoczynamy od maksymalnego
# przepływu równego zero
fmax = 0
# W pętli szukamy ścieżek
# rozszerzających dotąd, dopóki
# istnieją w sieci rezydualnej.
# Każda znaleziona ścieżka zwiększa
# przepływ wzdłuż zawartych w niej
# krawędzi grafu sieci przepływowej
while True:
    # Na początku pętli zerujemy
    # tablicę poprzedników PP
    pp = [-1] * n
    # Źródło nie posiada poprzednika.
    # Wpisujemy tutaj -2, aby BFS nie
    # wybierało źródła
    pp[s] = -2
    # Do CFP [s] wpisujemy największą
    # liczbę całkowitą
    cfp[s] = MAXINT
    # Zerujemy kolejkę i umieszczamy
    # w niej źródło s
    while not q.empty():
        q.pop()
    q.push(s)
    # Zmienna esc umożliwia odpowiednie
    # wychodzenie z dwóch zagnieżdżonych
    # pętli — zamiast polecenia goto.
    esc = False
    # Rozpoczynamy pętlę wyszukującą
    # ścieżki BFS. Pętla kończy się
    # w przypadku braku dalszych
    # wierzchołków w kolejce
    while not q.empty():
        # Z początku kolejki pobieramy
        # element i usuwamy go z kolejki
        x = q.front()
        q.pop()
        # Sprawdzamy wszystkich sąsiadów
        # wierzchołka x przeglądając
        # wiersz macierzy C
        for y in range(n):
            # Dla sąsiada y wyznaczamy
            # przepustowość rezydualną
            # krawędzi x->y. Jeśli krawędź
            # nie istnieje w sieci, to
            # otrzymamy w cp wynik zero
            cp = c[x][y] - f[x][y]
            # Sprawdzamy, czy krawędź
            # istnieje oraz czy wierzchołek
            # y nie był już wcześniej
            # wybrany przez BFS. W takim
            # przypadku PP [y] ma wartość
            # różną od -1.
            if cp != 0 and pp[y] == -1:
                # W PP [y] zapamiętujemy, iż
                # poprzednikiem y jest x
                pp[y] = x
                # Dla wierzchołka y obliczamy
                # dotychczasową przepustowość
                # rezydualną ścieżki. Jest to
                # mniejsza wartość
                # z przepustowości ścieżki dla
                # poprzednika x i bieżącej
                # przepustowości rezydualnej
                # krawędzi x->y.
                if cfp[x] > cp:
                    cfp[y] = cp
                else:
                    cfp[y] = cfp[x]
                # Jeśli osiągnęliśmy ujście,
                # to ścieżka jest kompletna
                if y == t:
                    # Zwiększamy przepływ
                    # maksymalny o przepustowość
                    # rezydualną ścieżki —
                    # wykorzystujemy tablicę CFP
                    fmax += cfp[t]
                    # Idziemy wstecz po ścieżce,
                    # zwiększając przepływy
                    # wzdłuż jej krawędzi
                    # w kierunku zgodnym ze
                    # ścieżką oraz zmniejszając
                    # przepływy w kierunku
                    # przeciwnym
                    i = y
                    while i != s:
                        x = pp[i]
                        f[x][i] += cfp[t]
                        f[i][x] -= cfp[t]
                        i = x
                    # Ustawiamy esc na true, co
                    # spowoduje wyjście z obu
                    # pętli
                    esc = True
                    break
                # Jeśli wierzchołek y nie jest
                # ujściem t, to dopisujemy go
                # na końcu kolejki Q
                # i kontynuujemy pętlę BFS
                q.push(y)
        # Tutaj wychodzimy z pętli while,
        # jeśli została znaleziona ścieżka
        # rozszerzająca
        if esc: break
    # Jeśli nie znaleziono ścieżki
    # rozszerzającej, to esc = false
    # i w tym miejscu nastąpi wyjście
    # z głównej pętli while
    if not esc: break
# Prezentujemy wyniki obliczeń.
# Najpierw wypisujemy wartość
# maksymalnego przepływu
print()
print("fmax =",fmax)
print()
# Następnie wypisujemy przepływy netto
# wzdłuż krawędzi
for x in range(n):
    for y in range(n):
        if c[x][y]:
            print(x," -> ",y," ",
                  f[x][y],":",c[x][y],
                  sep="")
print()
# Usuwamy zmienne dynamiczne
del c,f,pp,cfp

// Maksymalny przepływ
// Algorytm Edmondsa-Karpa
// Data: 24.08.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program maxflow;

// Definicja typu
// elementów listy
//----------------
type
  PSLel = ^SLel;
  SLel = record
    next  : PSLel;
    v, c, f : integer;
  end;

// Definicja typu
// obiektowego queue
//------------------
queue = object
  private
    head : PSLel;
    tail : PSLel;

  public
    constructor init;
    destructor  destroy;
    function    empty : boolean;
    function    front : integer;
    procedure   push (x : integer);
    procedure   pop;
end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor
//------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor
//-----------
destructor queue.destroy;
begin
  while not empty do
    pop;
end;

// Sprawdza, czy kolejka
// jest pusta
//----------------------
function queue.empty : boolean;
begin
  if head = nil then
    empty := true
  else
    empty := false;
end;

// Zwraca początek kolejki
// Wartość specjalna
// to -MAXINT
//------------------------
function queue.front : integer;
begin
  if head = nil then
    front := -MAXINT
  else
    front := head^.v;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(x : integer);
  var
    p : PSLel;
begin
  new(p);
  p^.next := nil;
  p^.v    := x;
  if tail = nil then
    head := p
  else
    tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
  var
    p : PSLel;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then
      tail := nil;
    dispose(p);
  end;
end;

//---------------
// Program główny
//---------------

var
  // Liczba krawędzi
  // i wierzchołków w grafie
  m, n : integer;
  // Tablica list sąsiedztwa
  L : array of PSLel;
  // Numer wierzchołka
  // źródła s i ujścia t
  s, t : integer;
  // Maksymalny przepływ
  // sieciowy
  fmax : integer;
  // Kolejka
  Q : queue;
  // Tablica poprzedników
  P : array of integer;
  // Tablica przepustowości
  // rezydualnych dla ścieżek
  CFP : array of integer;
  // Elementy pomocnicze
  i, cp, u, v : integer;
  // Wskaźniki elementów
  // listy sąsiedztwa
  x, z : PSLel;
  test : boolean;

begin
  Q.init;
  // Najpierw odczytujemy
  // liczbę wierzchołków
  // i krawędzi grafu
  read(n, m);
  // Tworzymy i inicjujemy
  // struktury dynamiczne
  //----------------------
  // Tablica wskaźników list
  SetLength(L, n);
  for i := 0 to n-1 do
    // Tablicę wypełniamy
    // pustymi listami
    L[i] := nil;
  SetLength(P, n);
  SetLength(CFP, n);
  // Teraz wczytujemy
  // definicje poszczególnych
  // krawędzi grafu. Każda
  // krawędź jest zdefiniowana
  // przez trzy liczby u, v i cp:
  // u  - wierzchołek początkowy
  //      krawędzi
  // v  - wierzchołek końcowy
  //      krawędzi
  // cp - przepustowość krawędzi
  for i := 1 to m do
  begin
    // Najpierw odczytujemy
    // te trzy liczby
    read(u, v, cp);
    // Tworzymy nowy
    // element listy
    new(x);
    // Wypełniamy jego
    // pola danych
    x^.v := v;
    x^.c := cp;
    // Zerujemy przepływ
    x^.f := 0;
    // Element dołączamy
    // do listy sąsiadów
    // wierzchołka u
    x^.next := L[u];
    L[u] := x;
  end;
  // Na koniec odczytujemy
  // numery wierzchołków
  // źródła i ujścia
  read(s, t);

  //*****************************
  //** Tutaj rozpoczyna się    **
  //** algorytm Edmondsa-Karpa **
  //*****************************

  // Zerujemy wartość maksymalnego
  // przepływu sieciowego
  fmax := 0;
  // Tworzymy w grafie strukturę
  // sieci rezydualnej
  for u := 0 to n-1 do
  begin
    x := L[u];
    while x <> nil do
    begin
      // Sprawdzamy, czy na liście
      // sąsiadów x jest wierzchołek u.
      // Jeśli tak, to krawędź zwrotna
      // istnieje i nie ma potrzeby
      // jej tworzenia.
      // Zakładamy brak
      // krawędzi zwrotnej
      test := false;
      z := L[x^.v];
      while z <> nil do
      begin
        if z^.v = u then
        begin
          test := true;
          break;
        end;
        z := z^.next;
      end;
      // Jeśli brak krawędzi,
      // tworzymy ją
      if not test then
      begin
        new(z);
        z^.v := u;
        z^.c := 0;
        z^.f := 0;
        z^.next := L[x^.v];
        L[x^.v] := z;
      end;
      x := x^.next;
    end;
  end;
  // Sieć rezydualna
  // została utworzona.
  // Teraz zajmiemy się
  // wyznaczeniem maksymalnych
  // przepływów w sieci.
  while true do
  begin
    for i := 0 to n-1 do
      // Zerujemy tablicę
      // poprzedników
      P[i] := -1;
    // Przepustowość źródła
    // jest nieskończona
    CFP[s] := MAXINT;
    // Zerujemy kolejkę
    while not Q.empty do
      Q.pop;
    // W kolejce umieszczamy
    // źródło s
    Q.push(s);
    // Szukamy ścieżki w sieci
    // rezudualnej od źródła
    // s do ujścia t
    while not Q.empty do
    begin
      // Zakładamy brak
      // takiej ścieżki
      test := false;
      // Pobieramy wierzchołek
      // z kolejki
      u := Q.front; Q.pop;
      // Przeglądamy listę
      // sąsiadów wierzchołka u
      x := L[u];
      while x <> nil do
      begin
        // Wyznaczamy przepustowość
        // rezydualną kanału
        cp := x^.c-x^.f;
        // Przetwarzamy tylko
        // istniejące i nieodwiedzone
        // jeszcze krawędzie
        if (cp <> 0) and
           (P[x^.v] = -1) then
        begin
          // Zapamiętujemy poprzednik
          // na ścieżce
          P[x^.v] := u;
          // Obliczamy przepustowość
          // rezydualną do węzła x^.v
          if cp < CFP[u] then
            CFP[x^.v] := cp
          else
            CFP[x^.v] := CFP[u];
          // Sprawdzamy, czy ścieżka
          // sięga do ujścia
          if x^.v = t then
          begin
            // Sygnalizujemy znalezioną
            // ścieżkę
            test := true;
            // Wychodzimy z pętli for
            break;
          end
          else
            // Inaczej umieszczamy
            // w kolejce wierzchołek
            // x^.v
            Q.push(x^.v);
        end;
        x := x^.next;
      end;
      // Jeśli jest ścieżka,
      // wychodzimy z pętli while
      if test then break;
    end;
    // Jeśli brak ścieżki,
    // kończymy algorytm
    if not test then break;
    // Zwiększamy przepływ sieciowy
    inc(fmax, CFP[t]);
    // Cofamy się po ścieżce
    // od ujścia t do źródła s
    v := t;
    while v <> s do
    begin
      // u jest poprzednikiem v
      // na ścieżce
      u := P[v];
      // Szukamy na liście
      // sąsiadów u krawędzi
      // prowadzącej do v.
      z := L[u];
      while z <> nil do
      begin
        if z^.v = v then
        begin
          // W kierunku zgodnym
          // ze ścieżką zwiększamy
          // przepływ
          inc(z^.f, CFP[t]);
          break;
        end;
        z := z^.next;
      end;
      // Szukamy na liście
      // sąsiadów v krawędzi
      // prowadzącej do u.
      z := L[v];
      while z <> nil do
      begin
        if z^.v = u then
        begin
          // W kierunku przeciwnym
          // do ścieżki zmniejszamy
          // przepływ
          dec (z^.f, CFP[t]);
          break;
        end;
        z := z^.next;
      end;
      v := u;
    end;
  end;
  // Prezentujemy wyniki obliczeń.
  // Najpierw wypisujemy wartość
  // maksymalnego przepływu
  writeln;
  writeln('fmax = ', fmax);
  writeln;
  // Następnie wypisujemy
  // znalezione przez algorytm
  // przepływy w kanałach pierwotnej
  // sieci przepływowej. Kanały
  // rozpoznajemy po niezerowej
  // wartości ich przepustowości.
  for i := 0 to n-1 do
  begin
    z := L[i];
    while z <> nil do
    begin
      if z^.c <> 0 then
        writeln(i, ' -> ', z^.v,
                ' ', z^.f, ':', z^.c);
      z := z^.next;
    end;
  end;
  writeln;
  // Koniec, usuwamy
  // struktury dynamiczne
  for i := 0 to n-1 do
  begin
    x := L[i];
    while x <> nil do
    begin
      z := x;
      x := x^.next;
      dispose(z);
    end;
  end;
  SetLength(L, 0);
  SetLength(P, 0);
  SetLength(CFP, 0);
  Q.destroy;
end.

// Maksymalny przepływ
// Algorytm Edmondsa-Karpa
// Data: 24.08.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

// Definicja typu elementów listy
//-------------------------------
struct SLel
{
  SLel * next;
  int v, c, f;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    SLel * head;
    SLel * tail;

  public:
    // konstruktor
    queue();
    // destruktor
    ~queue();
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor
//------------
queue::queue()
{
  head = tail = nullptr;
}

// Destruktor
//-----------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza,
// czy kolejka jest pusta
//-----------------------
bool queue::empty(void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front(void)
{
  if(head)
    return head->v;
  else
    return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int v)
{
  SLel * p = new SLel;
  p->next = nullptr;
  p->v = v;
  if(tail) tail->next = p;
  else head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop(void)
{
  if(head)
  {
    SLel * p = head;
    head = head->next;
    if(!head) tail = nullptr;
    delete p;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  // Liczba krawędzi
  // i wierzchołków w grafie
  int m, n;
  // Tablica list sąsiedztwa
  SLel ** L;
  // Numer wierzchołka
  // źródła s i ujścia t
  int s, t;
  // Maksymalny przepływ sieciowy
  int fmax;
  // Kolejka
  queue Q;
  // Tablica poprzedników
  int *P;
  // Tablica przepustowości
  // rezydualnych dla ścieżek
  int *CFP;
  // Elementy pomocnicze
  int i, cp, u, v;
  // Wskaźniki elementów
  // listy sąsiedztwa
  SLel *x, *z;
  bool test;
  // Najpierw odczytujemy
  // liczbę wierzchołków
  // i krawędzi grafu
  cin >> n >> m;
  // Tworzymy i inicjujemy
  // struktury dynamiczne
  //----------------------
  // Tablica wskaźników list
  L = new SLel * [n];
  for(i = 0; i < n; i++)
    // Tablicę wypełniamy
    // pustymi listami
    L[i] = nullptr;
  P = new int [n];
  CFP = new int [n];
  // Teraz wczytujemy definicje
  // poszczególnych krawędzi grafu.
  // Każda krawędź jest zdefiniowana
  // przez trzy liczby u, v i cp:
  // u  - wierzchołek początkowy
  //      krawędzi
  // v  - wierzchołek końcowy
  //      krawędzi
  // cp - przepustowość krawędzi
  for(i = 0; i < m; i++)
  {
    // Najpierw odczytujemy
    // te trzy liczby
    cin >> u >> v >> cp;
    // Tworzymy nowy element listy
    x = new SLel;
    // Wypełniamy jego pola danych
    x->v = v;
    x->c = cp;
    // Zerujemy przepływ
    x->f = 0;
    // Element dołączamy
    // do listy sąsiadów
    // wierzchołka u
    x->next = L[u];
    L[u] = x;
  }
  // Na koniec odczytujemy numery
  // wierzchołków źródła i ujścia
  cin >> s >> t;

  //*****************************
  //** Tutaj rozpoczyna się    **
  //** algorytm Edmondsa-Karpa **
  //*****************************

  // Zerujemy wartość maksymalnego
  // przepływu sieciowego
  fmax = 0;
  // Tworzymy w grafie strukturę
  // sieci rezydualnej
  for(u = 0; u < n; u++)
  {
    for(x = L[u]; x; x = x->next)
    {
      // Sprawdzamy, czy na liście
      // sąsiadów x jest wierzchołek
      // u. Jeśli tak, to krawędź
      // zwrotna istnieje i nie ma
      // potrzeby jej tworzenia.
      //----------------------------
      // Zakładamy brak krawędzi
      // zwrotnej
      test = false;
      for(z = L[x->v]; z; z = z->next)
        if(z->v == u)
        {
          test = true; break;
        }
      // Jeśli jest krawędź,
      // sprawdzamy kolejnego sąsiada
      if(test) continue;
      // Tworzymy krawędź zwrotną
      z = new SLel;
      z->v = u;
      z->c = z->f = 0;
      z->next = L[x->v];
      L[x->v] = z;
    }
  }
  // Sieć rezydualna została utworzona
  // Teraz zajmiemy się wyznaczeniem
  // maksymalnych przepływów w sieci.
  while(true)
  {
    for(i = 0; i < n; i++)
      // Zerujemy tablicę poprzedników
      P[i] = -1;
    // Przepustowość źródła
    // jest nieskończona
    CFP[s] = MAXINT;
    // Zerujemy kolejkę
    while(!Q.empty())
      Q.pop();
    // W kolejce umieszczamy źródło s
    Q.push(s);
    // Szukamy ścieżki w sieci
    // rezudualnej od źródła s
    // do ujścia t
    while(!Q.empty())
    {
      // Zakładamy brak
      // takiej ścieżki
      test = false;
      // Pobieramy wierzchołek
      // z kolejki
      u = Q.front(); Q.pop();
      // Przeglądamy listę sąsiadów
      // wierzchołka u
      for(x = L[u]; x; x = x->next)
      {
        // Wyznaczamy przepustowość
        // rezydualną kanału
        cp = x->c-x->f;
        // Przetwarzamy tylko
        // istniejące i nieodwiedzone
        // jeszcze krawędzie
        if(cp && (P[x->v] == -1))
        {
          // Zapamiętujemy poprzednik
          // na ścieżce
          P[x->v] = u;
          // Obliczamy przepustowość
          // rezydualną do węzła x->v
          CFP[x->v] = cp < CFP[u] ?
                      cp : CFP[u];
          // Sprawdzamy, czy ścieżka
          // sięga do ujścia
          if(x->v == t)
          {
             // Sygnalizujemy
             // znalezioną ścieżkę
             test = true;
             // Wychodzimy z pętli for
             break;
          }
          else
            // Inaczej umieszczamy
            // w kolejce wierzchołek
            // x->v
            Q.push(x->v);
        }
      }
      // Jeśli jest ścieżka,
      // wychodzimy z pętli while
      if(test) break;
    }
    // Jeśli brak ścieżki,
    // kończymy algorytm
    if(!test) break;
    // Zwiększamy przepływ sieciowy
    fmax += CFP[t];
    // Cofamy się po ścieżce
    // od ujścia t do źródła s
    for(v = t; v != s; v = u)
    {
      // u jest poprzednikiem v
      // na ścieżce
      u = P[v];
      // Szukamy na liście
      // sąsiadów u krawędzi
      // prowadzącej do v.
      for(z = L[u]; z; z = z->next)
        if(z->v == v)
        {
          // W kierunku zgodnym
          //ze ścieżką zwiększamy
          // przepływ
          z->f += CFP[t];
          break;
        }
      // Szukamy na liście
      // sąsiadów v krawędzi
      // prowadzącej do u.
      for(z = L[v]; z; z = z->next)
        if(z->v == u)
        {
          // W kierunku przeciwnym
          // do ścieżki zmniejszamy
          // przepływ
          z->f -= CFP[t];
          break;
        }
    }
  }
  // Prezentujemy wyniki obliczeń.
  // Najpierw wypisujemy wartość
  // maksymalnego przepływu
  cout << "\nfmax = " << fmax
       << endl << endl;
  // Następnie wypisujemy znalezione
  // przez algorytm przepływy w
  // kanałach pierwotnej sieci
  // przepływowej. Kanały rozpoznajemy
  // po niezerowej wartości ich
  // przepustowości.
  for(i = 0; i < n; i++)
    for(z = L[i]; z; z = z->next)
      if(z->c)
        cout << i << " -> " << z->v
             << " " << z->f << ":"
             << z->c << endl;
  cout << endl;
  // Koniec, usuwamy
  // struktury dynamiczne
  for(i = 0; i < n; i++)
  {
    x = L[i];
    while(x)
    {
      z = x;
      x = x->next;
      delete z;
    }
  }
  delete [] L;
  delete [] P;
  delete [] CFP;
  return 0;
}

' Maksymalny przepływ
' Agorytm Edmondsa-Karpa
' Data: 24.08.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

Const MAXINT = 2147483647

' Definicja typu elementów listy
'-------------------------------
Type SLel
  next As SLel Ptr
  v As Integer
  c As Integer
  f As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As SLel Ptr
    tail As SLel Ptr

  Public:
    Declare Constructor
    Declare Destructor
    Declare Function empty As Integer
    Declare Function front As Integer
    Declare Sub push(ByVal x As Integer)
    Declare Sub pop
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor
'------------
Constructor queue
  head = 0
  tail = 0
End Constructor

' Destruktor-usuwa listę z pamięci
'---------------------------------
Destructor queue
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty As Integer
  If head = 0 Then Return -1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->v
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal v As Integer)
  Dim p As SLel Ptr
  p = new SLel
  p->next = 0
  p->v = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop
  Dim p As SLel Ptr
  If head <> 0 Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

'---------------
' Program główny
'---------------

' Liczba krawędzi
' i wierzchołków w grafie
Dim As Integer m, n
' Tablica list sąsiedztwa
Dim As SLel Ptr Ptr L
' Numer wierzchołka
' źródła s i ujścia t
Dim As Integer s, t
' Maksymalny przepływ sieciowy
Dim As Integer fmax
' Kolejka
Dim As queue Q
' Tablica poprzedników
Dim As Integer Ptr P
' Tablica przepustowości
' rezydualnych dla ścieżek
Dim As Integer Ptr CFP
' Elementy pomocnicze
Dim As Integer i, cp, u, v
' Wskaźniki elementów
' listy sąsiedztwa
Dim As SLel Ptr x, z
Dim As Integer test

' Najpierw odczytujemy
' liczbę wierzchołków
' i krawędzi grafu
Open Cons For Input As #1
Input #1, n, m
' Tworzymy i inicjujemy
' struktury dynamiczne
'----------------------
' Tablica wskaźników list
L = New SLel Ptr [n]
For i = 0 To n-1
  ' Tablicę wypełniamy
  ' pustymi listami
  L[i] = 0
Next
P = New Integer [n]
CFP = New Integer [n]
' Teraz wczytujemy definicje
' poszczególnych krawędzi grafu.
' Każda krawędź jest zdefiniowana
' przez trzy liczby u, v i cp:
' u  - wierzchołek początkowy krawędzi
' v  - wierzchołek końcowy krawędzi
' cp - przepustowość krawędzi
For i = 1 To m
  ' Najpierw odczytujemy
  ' te trzy liczby
  Input #1, u, v, cp
  ' Tworzymy nowy element listy
  x = New SLel
  ' Wypełniamy jego pola danych
  x->v = v
  x->c = cp
  ' Zerujemy przepływ
  x->f = 0
  ' Element dołączamy
  ' do listy sąsiadów
  ' wierzchołka u
  x->next = L[u]
  L[u] = x
Next
' Na koniec odczytujemy
' numery wierzchołków
' źródła i ujścia
Input #1, s, t

'*****************************
'** Tutaj rozpoczyna się    **
'** algorytm Edmondsa-Karpa **
'*****************************

' Zerujemy wartość maksymalnego
' przepływu sieciowego
fmax = 0
' Tworzymy w grafie strukturę
' sieci rezydualnej
For u = 0 To n-1
  x = L[u]
  While x <> 0
    ' Sprawdzamy, czy na liście
    ' sąsiadów x jest wierzchołek u.
    ' Jeśli tak, to krawędź zwrotna
    ' istnieje i nie ma potrzeby
    ' jej tworzenia.
    '-------------------------------
    ' Zakładamy brak krawędzi zwrotnej
    test = 0
    z = L[x->v]
    While z
      If z->v = u Then
        test = 1
        Exit While
      End If
      z = z->next
    Wend
    ' Jeśli brak krawędzi,
    ' tworzymy ją
    If test = 0 Then
      z = New SLel
      z->v = u
      z->c = 0
      z->f = 0
      z->next = L[x->v]
      L[x->v] = z
    End If
    x = x->next
  Wend
Next
' Sieć rezydualna została utworzona.
' Teraz zajmiemy się wyznaczeniem
' maksymalnych przepływów w sieci.
While 1
  For i = 0 To n-1
    ' Zerujemy tablicę poprzedników
    P[i] = -1
  Next
  ' Przepustowość źródła
  ' jest nieskończona
  CFP[s] = MAXINT
  While Not Q.empty
    ' Zerujemy kolejkę
    Q.pop
  Wend
  ' W kolejce umieszczamy źródło s
  Q.push(s)
  ' Szukamy ścieżki
  ' w sieci rezudualnej
  ' od źródła s do ujścia t
  While Not Q.empty
    ' Zakładamy brak takiej ścieżki
    test = 0
    ' Pobieramy wierzchołek z kolejki
    u = Q.front: Q.pop
    ' Przeglądamy listę
    ' sąsiadów wierzchołka u
    x = L[u]
    While x <> 0
      ' Wyznaczamy przepustowość
      ' rezydualną kanału
      cp = x->c - x->f
      ' Przetwarzamy tylko istniejące
      ' i nieodwiedzone jeszcze krawędzie
      if (cp <> 0) AndAlso _
         (P[x->v] = -1) Then
        ' Zapamiętujemy poprzednik
        ' na ścieżce
        P[x->v] = u
        ' Obliczamy przepustowość
        ' rezydualną do węzła x->v
        If cp < CFP[u] Then
          CFP[x->v] = cp
        Else
          CFP[x->v] = CFP[u]
        EndIf
        ' Sprawdzamy, czy ścieżka
        ' sięga do ujścia
        If x->v = t Then
          ' Sygnalizujemy znalezioną
          ' ścieżkę
          test = 1
          ' Wychodzimy z pętli
          Exit While
        Else
          ' Inaczej umieszczamy
          ' w kolejce wierzchołek x->v
          Q.push(x->v)
        End If
      End If
      x = x->next
    Wend
    ' Jeśli jest ścieżka,
    ' wychodzimy z pętli while
    If test = 1 Then Exit While
  Wend
  ' Jeśli brak ścieżki,
  ' kończymy algorytm
  If test = 0 Then Exit While
  ' Zwiększamy przepływ sieciowy
  fmax += CFP[t]
  ' Cofamy się po ścieżce
  ' od ujścia t do źródła s
  v = t
  While v <> s
    ' u jest poprzednikiem v na ścieżce
    u = P[v]
    ' Szukamy na liście sąsiadów u
    ' krawędzi prowadzącej do v.
    z = L[u]
    While z
      If z->v = v Then
        ' W kierunku zgodnym
        ' ze ścieżką zwiększamy
        ' przepływ
        z->f += CFP[t]
        Exit While
      End If
      z = z->next
    Wend
    ' Szukamy na liście sąsiadów v
    ' krawędzi prowadzącej do u.
    z = L[v]
    While z
      If z->v = u Then
        ' W kierunku przeciwnym
        ' do ścieżki zmniejszamy
        ' przepływ
        z->f -= CFP[t]
        Exit While
      End If
      z = z->next
    Wend
    v = u
  Wend
Wend

' Prezentujemy wyniki obliczeń.
' Najpierw wypisujemy wartość
' maksymalnego przepływu
Print
Print "fmax =";fmax
Print
' Następnie wypisujemy znalezione
' przez algorytm przepływy w
' kanałach pierwotnej sieci
' przepływowej. Kanały rozpoznajemy
' po niezerowej wartości ich
' przepustowości.
For i = 0 To n-1
  z = L[i]
  While z
    If z->c Then _
      Print Using "& -> & &:&";i; _
                  z->v;z->f;z->c
    z = z->next
  Wend
Next
Print
' Koniec, usuwamy
' struktury dynamiczne
For i = 0 To n-1
  x = L[i]
  While x
    z = x
    x = x->next
    Delete z
  Wend
Next
Delete [] L
Delete [] P
Delete [] CFP
End

# Maksymalny przepływ
# Agorytm Edmondsa-Karpa
# Data: 07.04.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

MAXINT = 2147483647

# Definicja elementu listy
# -------------------------
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0
        self.c = 0
        self.f = 0

# Definicja obiektu Queue
#------------------------
class Queue:
    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None

    # Destruktor
    def __del__(self):
        while not self.empty():
            self.pop()

    # Sprawdza,
    # czy kolejka jest pusta
    def empty(self):
        return not self.head

    # Zwraca początek kolejki.
    # Wartość specjalna to -MAXINT
    def front(self):
        global MAXINT
        if not self.head:
            return -MAXINT
        else:
            return self.head.v

    # Zapisuje do kolejki
    def push(self, v):
        p = SLel()
        p.next = None
        p.v = v
        if not self.tail:
            self.head = p
        else:
            self.tail.next = p
        self.tail = p

    # Usuwa z kolejki
    def pop(self):
        if self.head:
            self.head = self.head.next
            if not self.head:
                self.tail = None

#---------------
# Program główny
#---------------

# Kolejka
q = Queue()
# Najpierw odczytujemy
# liczbę wierzchołków
# i krawędzi grafu
r = input().split()
n = int(r[0])
m = int(r[1])
# Tworzymy i inicjujemy
# struktury dynamiczne
#----------------------
# Tablica wskaźników list
tl = [None] * n
tp = [0] * n
cfp = [0] * n
# Teraz wczytujemy definicje
# poszczególnych krawędzi grafu.
# Każda krawędź jest zdefiniowana
# przez trzy liczby u, v i cp:
# u — wierzchołek początkowy krawędzi
# v — wierzchołek końcowy krawędzi
# cp — przepustowość krawędzi
for i in range(m):
    # Najpierw odczytujemy
    # te trzy liczby
    r = input().split()
    u = int(r[0])
    v = int(r[1])
    cp = int(r[2])
    # Tworzymy nowy element listy
    x = SLel()
    # Wypełniamy jego pola danych
    x.v = v
    x.c = cp
    # Zerujemy przepływ
    x.f = 0
    # Element dołączamy
    # do listy sąsiadów
    # wierzchołka u
    x.next = tl[u]
    tl[u] = x
# Na koniec odczytujemy
# numery wierzchołków
# źródła i ujścia
r = input().split()
s = int(r[0])
t = int(r[1])

#*****************************
#** Tutaj rozpoczyna się    **
#** algorytm Edmondsa-Karpa **
#*****************************

# Zerujemy wartość maksymalnego
# przepływu sieciowego
fmax = 0
test = False
# Tworzymy w grafie strukturę
# sieci rezydualnej
for u in range(n):
    x = tl[u]
    while x:
        # Sprawdzamy, czy na liście
        # sąsiadów x jest wierzchołek u.
        # Jeśli tak, to krawędź zwrotna
        # istnieje i nie ma potrzeby
        # jej tworzenia.
        #-------------------------------
        # Zakładamy brak
        # krawędzi zwrotnej
        test = False
        z = tl[x.v]
        while z:
            if z.v == u:
                test = True
                break
            z = z.next
        # Jeśli brak krawędzi,
        # tworzymy ją
        if not test:
            z = SLel()
            z.v = u
            z.c = 0
            z.f = 0
            z.next = tl[x.v]
            tl[x.v] = z
        x = x.next
# Sieć rezydualna została utworzona.
# Teraz zajmiemy się wyznaczeniem
# maksymalnych przepływów w sieci.
while True:
    tp = [-1] * n
    # Przepustowość źródła
    # jest nieskończona
    cfp[s] = MAXINT
    while not q.empty():
        # Zerujemy kolejkę
        q.pop()
    # W kolejce umieszczamy źródło s
    q.push(s)
    # Szukamy ścieżki
    # w sieci rezudualnej
    # od źródła s do ujścia t
    while not q.empty():
        # Zakładamy brak takiej ścieżki
        test = False
        # Pobieramy wierzchołek z kolejki
        u = q.front()
        q.pop()
        # Przeglądamy listę
        # sąsiadów wierzchołka u
        x = tl[u]
        while x:
            # Wyznaczamy przepustowość
            # rezydualną kanału
            cp = x.c - x.f
            # Przetwarzamy tylko
            # istniejące
            # i nieodwiedzone krawędzie
            if cp and tp[x.v] == -1:
                # Zapamiętujemy
                # poprzednik na ścieżce
                tp[x.v] = u
                # Obliczamy przepustowość
                # rezydualną do węzła x.v
                if cp < cfp[u]:
                    cfp[x.v] = cp
                else:
                    cfp[x.v] = cfp[u]
                # Sprawdzamy, czy ścieżka
                # sięga do ujścia
                if x.v == t:
                    # Sygnalizujemy
                    # znalezioną ścieżkę
                    test = True
                    # Wychodzimy z pętli
                    break
                else:
                    # Inaczej umieszczamy
                    # w kolejce
                    # wierzchołek x.v
                    q.push(x.v)
            x = x.next
        # Jeśli jest ścieżka,
        # wychodzimy z pętli while
        if test: break
    # Jeśli brak ścieżki,
    # kończymy algorytm
    if not test: break
    # Zwiększamy przepływ sieciowy
    fmax += cfp[t]
    # Cofamy się po ścieżce
    # od ujścia t do źródła s
    v = t
    while v != s:
        # u jest poprzednikiem v
        # na ścieżce
        u = tp[v]
        # Szukamy na liście sąsiadów u
        # krawędzi prowadzącej do v.
        z = tl[u]
        while z:
            if z.v == v:
                # W kierunku zgodnym
                # ze ścieżką zwiększamy
                # przepływ
                z.f += cfp[t]
                break
            z = z.next
        # Szukamy na liście sąsiadów v
        # krawędzi prowadzącej do u.
        z = tl[v]
        while z:
            if z.v == u:
                # W kierunku przeciwnym
                # do ścieżki zmniejszamy
                # przepływ
                z.f -= cfp[t]
                break
            z = z.next
        v = u
# Prezentujemy wyniki obliczeń.
# Najpierw wypisujemy wartość
# maksymalnego przepływu
print()
print("fmax =",fmax)
print()
# Następnie wypisujemy znalezione
# przez algorytm przepływy w
# kanałach pierwotnej sieci
# przepływowej. Kanały rozpoznajemy
# po niezerowej wartości ich
# przepustowości.
for i in range(n):
    z = tl[i]
    while z:
        if z.c:
            print(i," . ",z.v," ",
                  z.f,":",z.c,sep="")
        z = z.next
print()
# Koniec, usuwamy
# struktury dynamiczne
for i in range(n):
    while tl[i]:
        tl[i] = tl[i].next
del tl,tp,cfp