No dataset at present.

Description

Use python3 to implement Edmonds Karp algorithm that solves the Maximum Bi-partition Matching Problem

Submission Format

Submit a tar or zip file including a script named BiPartition.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

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

Output

9