题目描述

给定一张 $n$ 个点、$m$ 条边的有向图，结点编号 $1\sim n$，每条边有一个非负整数容量 $c$。给定源点 $s$ 与汇点 $t$，请你求出从 $s$ 到 $t$ 的最大流。

图中可能存在重边，也可能存在容量为 $0$ 的边，还可能出现 $s$ 到不了 $t$ 的情况。

输入格式

第一行四个整数 $n,m,s,t$。

接下来 $m$ 行，每行三个整数 $u,v,c$，表示一条从 $u$ 到 $v$、容量为 $c$ 的有向边。

输出格式

一行一个整数，表示最大流。

输入输出样例 #1

输入 #1

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

输出 #1

5

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 10^4$，$0\le m\le 10^5$，$0\le c\le 10^9$，$s\ne t$。