Maximum Flow Problem

You are given a directed graph with \(n\) vertices and \(m\) edges. Each edge has a given capacity. Your task is to calculate the maximum flow from a source vertex \(s\) to a target vertex \(t\). Note that the graph may contain multiple edges (parallel edges) between two vertices.

The maximum flow is defined as:

[ \max f(s,t) ]

where the flow on each edge does not exceed its capacity, and the flow is conserved at every vertex except \(s\) and \(t\).

inputFormat

The first line contains four integers \(n\), \(m\), \(s\), and \(t\), where \(n\) is the number of vertices, \(m\) is the number of edges, \(s\) is the source vertex, and \(t\) is the target vertex. The vertices are numbered from 1 to \(n\).

Then \(m\) lines follow. Each of these lines contains three integers \(u\), \(v\), and \(c\) indicating that there is a directed edge from vertex \(u\) to vertex \(v\) with a capacity of \(c\).

outputFormat

Output a single integer, the maximum flow from vertex \(s\) to vertex \(t\).

sample

4 5 1 4
1 2 100
1 3 100
2 3 1
2 4 100
3 4 100

200