#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef pair<int, int> ii; // weight and Node
typedef vector<ii> vii; //agjlist

int maxFlow(vector<vii> AdjList, int s, int t);

int main()
{
    vector<vii> AdjList;

    int V, s, t;
    cout<<"vertex=";
    cin >> V ;
    cout<<"Sort Node";
    cin >> s ;
    cout<<"Sing Node";
    cin >> t;

    AdjList.assign(V, vii());


    for (int u = 0; u < V; u++)
    {

        int K;
        cout<<"K(Line)=";
        cin >> K ;

        for (int k = 0; k < K; k++)
        {
            int v, w;
            cout<<"vertex="
            cin >> v
            cout>>"Weight";
            cin >> w;

            AdjList[u].push_back(make_pair(w, v));
        }
    }
    // input Node S T

    cout << "Max flow is " << maxFlow(AdjList, s, t) << "\n";

    return 0;
}

int maxFlow(vector<vii> AdjList, int s, int t) //graph S T
{
    int maxflow = 0;
    int V = AdjList.size(); //Node number
    int residual[V][V]; //maxtirx v*v

    // Create residual matrix
    memset(residual, 0, sizeof residual); // all element  at 0
    for (int u = 0; u < V; u++)
    {
        //
        for (size_t k = 0; k < AdjList[u].size(); k++) //size_t = int
        {
            int v = AdjList[u][k].second;
            int w = AdjList[u][k].first;

            residual[u][v] = w; // U -> V=W
        }
    }

    // Edmonds-Karp
    while(1)
    {
        //BFS
        vector<bool> visited; // Give Node go
        vector<int> parent; // Go Node streen
        vector<int> bottleneck; // result of Go Node streen

        visited.assign(V, false);// defaut dont go  false
        parent.assign(V, -1); //No go dont parent
        bottleneck.assign(V, INT_MAX); // INF -> min
        //----------------------------------------------------------------//
        // BFS + save path + propagate bottleneck
        queue<int> q; // open give Node
        q.push(s);
        visited[s] = true;

        while(!q.empty())//cheak  true emty
        {
            int u = q.front(); // Node u pop u
            q.pop();

            if (u == t) break; // found the sink node // T node Stop

            for (size_t k = 0; k < AdjList[u].size(); k++)//Node shit u
            {
                int v = AdjList[u][k].second;
                int availableFlow = residual[u][v];

                if ((availableFlow > 0) && (!visited[v]))
                {
                    visited[v] = true;
                    parent[v] = u;
                    bottleneck[v] = min(bottleneck[u], availableFlow);
                    //
                    q.push(v);
                }
            }
        }

        // No more way // T
        if (!visited[t] || bottleneck[t] == 0)
            break;

        // propagate bottleneck
        int k = t;
        while (parent[k] != -1)
        {
            cout << k << " <- ";
            residual[parent[k]][k] -= bottleneck[t];
            residual[k][parent[k]] += bottleneck[t];

            k = parent[k];
        }
        cout << " Bottleneck = " << bottleneck[t] << "\n";

        // accumulate flow
        maxflow += bottleneck[t];
    }

    return maxflow;
}