/**
 * Maria Sales Nš 41748 MIEI
 * Ricardo Silva Nš 37798 LEI
 */

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class Graph {

	private List<Integer>[] edges;
	private int nVertices;
	
	@SuppressWarnings("unchecked")
	public Graph(int nVertices, int nArcs) {
		this.nVertices = nVertices;
		edges = new LinkedList[nVertices];
		
		for(int i = 0; i < nVertices; i++){
			edges[i] = new LinkedList<Integer>();
		}
	}

	public void addArc(int v1, int v2) {
		edges[v1].add(v2);		
		edges[v2].add(v1);	
		
	}

	public boolean process(int nRoads, int vi, int vf) {

		int[][] flow = new int[nVertices][nVertices];
		
	//	for(int i = 0; i < nVertices; i++){
	//		for(int e: edges[i])			
	//			flow[i][e] = 0;
	//	}
		
		int[] via = new int[nVertices];
		
		int flowValue = 0;
		int increment;
		
		while((increment = findPath(vi, vf, via, flow)) != 0){
			flowValue += increment;
			
			// Update flow			
			int v = vf;
			
			while( v != vi){
				int origin = via[v];
				
				flow[origin][v] += increment;
				flow[v][origin] -= increment;
				
				v = origin;
			}
		}
		
		return (flowValue - nRoads) > 0;
	}
	
	int findPath(int source, int sink, int[] via, int[][] flow){
		
		Queue<Integer> waiting = new LinkedList<Integer>();
		
		boolean[] found = new boolean[nVertices];
		
		int[] pathIncr = new int[nVertices];
		
		waiting.add(source);
		
		found[source] = true;
		
		via[source] = source;
		
		pathIncr[source] = Integer.MAX_VALUE;
		
		do{
			
			int origin = waiting.remove();
			
			for(int e: edges[origin]){
				int destin = e;
				
				int residue = 1 - flow[origin][destin];
				
				if(!found[destin] && residue > 0){
					via[destin] = origin;
					pathIncr[destin] = Math.min(pathIncr[origin], residue);
					
					if ( destin == sink )
						return pathIncr[destin];
						waiting.add(destin);
						found[destin] = true;
				}
			}
			
		} while(!waiting.isEmpty());
		
		return 0;
	}


}