You cannot submit for this problem because the homework's deadline is due.

Description

Use python3 to implement Edmonds Karp algorithm.

Submission Format

Submit a tar or zip file including a script named EdmondsKarp.py and all the related class you have implemented. There are no restriction on the filenames of your imported classes.

IO

Input

The first line contains the number of edges edge_num.
Starting from the second line, information of directed edges will be provided in the form of nodeA nodeB weight.
The final two lines will give you the start and terminate node.

Output

The maximum flow ( a single integer value )

Sample IO

Sample 1

input

4
s d 10
s c 9
d t 8
c t 9
s
t

Output

17