/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication1;

import java.io.File;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

/**
 *
 * @author 5730213093
 */
public class NewClass1 {

    public static void main(String[] args) throws Exception {
        if (args.length != 1) {
            System.out.println("Usage: java EdmondsKarp <data-file>");
            return;
        }

        Scanner sc = new Scanner(new File(args[0]));
        int numVs = sc.nextInt();
        int source = sc.nextInt();
        int sink = sc.nextInt();

        // build residual graph without creating an ordinary graph first
        int[][] rGraph = new int[numVs][numVs];
        for (int u = 0; u < numVs; u++) {
            int numNeighbors = sc.nextInt();
            for (int j = 0; j < numNeighbors; j++) {
                rGraph[u][sc.nextInt()] = sc.nextInt();   // (u, v) = weight
            }
        }

        System.out.println("The maximum possible flow is "
                + edmondsKarp(rGraph, source, sink));
    }  // end of main()

    public static int edmondsKarp(int[][] rGraph, int s, int t) {
        int maxFlow = 0;
        // Augment the flow while there is a path from source to sink
        ArrayList<IPair> path = null;
        while ((path = findShortestPath(rGraph, s, t)) != null) {
            System.out.print("Found: ");
            for (IPair p : path) {
                System.out.print(p.getX() + " -> ");
            }
            System.out.println(t);

            // Find minimum residual capacity of the edges along the path
            int bottleneck = Integer.MAX_VALUE;
            for (IPair p : path) {
                bottleneck = Math.min(bottleneck, rGraph[p.getX()][p.getY()]);
            }
            System.out.println("  Bottlneck: " + bottleneck);

            // update residual capacities along the path
            for (IPair p : path) {
                int u = p.getX();
                int v = p.getY();
                rGraph[u][v] -= bottleneck;   // forward edge
                rGraph[v][u] += bottleneck;   // backward edge
            }
            maxFlow += bottleneck;
        }
        return maxFlow;
    }  // end of edmondsKarp()

    public static ArrayList<IPair> findShortestPath(int[][] rGraph,
            int s, int t) /* Returns the shortest augmented path from source s to sink t
     in the residual graph. */ {
        // set all of visited array as not visited
        int numVs = rGraph.length;
        boolean visited[] = new boolean[numVs];  // false by default
        int parentOf[] = new int[numVs];

        // enqueue source and mark as visited
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.add(s);
        visited[s] = true;
        parentOf[s] = -1;
        // BFS implemented using a queue and a loop
        while (queue.size() != 0) {
            int u = queue.poll();
            for (int v = 0; v < numVs; v++) {
                if ((!visited[v]) && (rGraph[u][v] > 0)) {
                    /* there's some residual capacity available for
                     visiting the unvisited v */
                    queue.add(v);
                    parentOf[v] = u;
                    visited[v] = true;
                }
            }
        }
        if (visited[t]) {   // have we got from source to sink?
            ArrayList<IPair> path = new ArrayList<IPair>();
            for (int v = t; v != s; v = parentOf[v]) // from t to s
            {
                path.add(0, new IPair(parentOf[v], v));   // add (u,v) so in rev order
            }
            return path;
        } else {
            return null;
        }
    }  // end of findShortestPath()

}
class IPair
{
    private int x;
    private int y;
    public IPair(int x,int y) {
        this.x=x;
        this.y=y;
    }
    int getX()
    {
        return x;
    }
    int getY()
    {
        return y;
    }

}