给定一个有向图,由 n 个顶点和 m 个边组成。顶点 s 和 t 分别标记为源和汇。此外,不存在以 s 结束的边,也不存在以 t 开始的边。
该图是按以下方式构建的:最初,每条边的容量 ci > 0。在此流网络中构建了源位于 s 、汇位于 t 的最大流。我们将 fi 表示为通过索引为 i 的边的流量值。接下来,所有容量ci和流量值fi被擦除。相反,指标 gi 写在边上——如果通过边 i 的流量值为正,即如果 fi > 0 则为 1,否则为 0。
使用图形和值 gi,找出初始流量网络中可能饱和的最小可能边数是多少(通过的流量等于容量,即 fi = ci)。并构建相应的流量网络,其中流量最大。
有向图中的流由每条边上的流值 fi 描述,从而满足以下条件:
- 对于每个顶点,除了源和汇之外,总流入流量和总流出流量相等,
- 对于每条边 0 ≤ fi ≤ ci
如果来自源的边上的流量值之和与到源的边上的流量值之和(本问题中没有这样的情况)之间的差值是最大可能的,则流量是最大的。
输入
输入数据的第一行包含四个正整数 n, m, s, t (2 ≤ n ≤ 100, 1 ≤ m ≤ 1000, 1 ≤ s, t ≤ n, s ≠ t) — 对应的顶点数、边数、源顶点索引和汇顶点索引。
接下来 m 行输入数据中的每一行都包含非负整数 ui, vi, gi (1 ≤ ui, vi ≤ n, $$g_i \in \{0, 1\}$$) — 边 i 的开头、边 i 的结尾和指示符,如果通过边 i 的流量值为正,则等于 1,否则等于 0。
保证没有边将顶点与其自身连接。此外,还保证每个有序顶点对之间不存在超过一条边,并且至少存在一个满足输入数据的所有约束的网络流。
输出
在第一行中打印单个非负整数 k — 最小边数,在最大流中应饱和。
在接下来的 m 行中,每一行打印两个整数 fi, ci (1 ≤ ci ≤ 109, 0 ≤ fi ≤ ci) — 通过边 i 的流量值和边 i 的容量。
该数据应在流量网络中形成正确的最大流量。此外,必须恰好有 k 条边满足 fi = ci 语句。另外,当且仅当 gi = 1 时,语句 fi > 0 必须为真。
如果有多个可能的答案,请打印其中任何一个。
示例
输入 #1
5 6 1 5 1 2 1 2 3 1 3 5 1 1 4 1 4 3 0 4 5 1
输出 #1
2 3 3 3 8 3 4 4 4 0 5 4 9
注意
第二个示例案例的插图。饱和的边缘标记为黑色,而 gi = 0 的边缘标记为虚线。边上的整数是该边在输入列表中的索引。