CF843E.Maximum Flow

You are given a directed graph, consisting of n vertices and m edges. The vertices s and t are marked as source and sink correspondingly. Additionally, there are no edges ending at s and there are no edges beginning in t.

The graph was constructed in a following way: initially each edge had capacity c__i > 0. A maximum flow with source at s and sink at t was constructed in this flow network. Let's denote f__i as the value of flow passing through edge with index i. Next, all capacities c__i and flow value f__i were erased. Instead, indicators g__i were written on edges — if flow value passing through edge i was positive, i.e. 1 if f__i > 0 and 0 otherwise.

Using the graph and values g__i, find out what is the minimum possible number of edges in the initial flow network that could be saturated (the passing flow is equal to capacity, i.e. f__i = c__i). Also construct the corresponding flow network with maximum flow in it.

A flow in directed graph is described by flow values f__i on each of the edges so that the following conditions are satisfied:

• for each vertex, except source and sink, total incoming flow and total outcoming flow are equal,
• for each edge 0 ≤ f__i ≤ c__i

A flow is maximum if the difference between the sum of flow values on edges from the source, and the sum of flow values on edges to the source (there are no such in this problem), is maximum possible.

给你一个有向图，包含 $n$ 个顶点和 $m$ 条边。其中顶点 $s$ 和 $t$ 分别被标记为源点（source）和汇点（sink）。此外，没有边以 $s$ 为终点，也没有边以 $t$ 为起点。

该图是按如下方式构造的：最初每条边具有容量 $c_i > 0$。在此流网络中，构造了一个以 $s$ 为源点、$t$ 为汇点的最大流。记 $f_i$ 为经过编号为 $i$ 的边的流量值。接着，所有容量 $c_i$ 和流量值 $f_i$ 均被擦除。取而代之的是，在每条边上写下了指示器 $g_i$ —— 若经过第 $i$ 条边的流量为正，则 $g_i = 1$；否则 $g_i = 0$（即 $g_i = 1$ 当且仅当 $f_i > 0$）。

利用该图及各 $g_i$ 值，请确定初始流网络中可能被饱和（即流值等于容量，亦即 $f_i = c_i$）的边的最少数量。同时，请构造一个满足该最小数量的对应流网络，并给出其中的最大流。

有向图中的一个流由每条边上的流量值 $f_i$ 描述，且需满足以下条件：

• 对每个非源点、非汇点的顶点，其总入流等于总出流；
• 对每条边，满足 $0 \leq f_i \leq c_i$。

一个流被称为最大流，当且仅当从源点出发的所有边上的流量之和（减去流入源点的所有边上的流量之和；本题中后者为 0）达到可能的最大值。

The first line of input data contains four positive integers n, m, s, t (2 ≤ n ≤ 100, 1 ≤ m ≤ 1000, 1 ≤ s, t ≤ n, s ≠ t) — the number of vertices, the number of edges, index of source vertex and index of sink vertex correspondingly.

Each of next m lines of input data contain non-negative integers u__i, v__i, g__i (1 ≤ u__i, v__i ≤ n, ) — the beginning of edge i, the end of edge i and indicator, which equals to 1 if flow value passing through edge i was positive and 0 if not.

It's guaranteed that no edge connects vertex with itself. Also it's guaranteed that there are no more than one edge between each ordered pair of vertices and that there exists at least one network flow that satisfies all the constrains from input data.

输入数据的第一行包含四个正整数 $n$、$m$、$s$、$t$（满足 $2 \leq n \leq 100$，$1 \leq m \leq 1000$，$1 \leq s, t \leq n$，且 $s \neq t$），分别表示顶点数、边数、源点顶点编号和汇点顶点编号。

接下来的 $m$ 行每行包含三个非负整数 $u_i$、$v_i$、$g_i$（满足 $1 \leq u_i, v_i \leq n$，且 ）—— 分别表示第 $i$ 条边的起点、终点，以及一个指示符：若流经第 $i$ 条边的流量值为正，则该指示符为 $1$；否则为 $0$。

保证不存在连接顶点到其自身的边。同时保证任意一对有序顶点之间至多存在一条边，且至少存在一个网络流满足输入数据中的所有约束条件。

In the first line print single non-negative integer k — minimum number of edges, which should be saturated in maximum flow.

In each of next m lines print two integers f__i, c__i (1 ≤ c__i ≤ 109, 0 ≤ f__i ≤ c__i) — the flow value passing through edge i and capacity of edge i.

This data should form a correct maximum flow in flow network. Also there must be exactly k edges with statement f__i = c__i satisfied. Also statement f__i > 0 must be true if and only if g__i = 1.

If there are several possible answers, print any of them.

第一行输出一个非负整数 $k$ —— 最大流中必须饱和的边的最少数量。

接下来的 $m$ 行中，每行输出两个整数 $f_i,\,c_i$（其中 $1 \le c_i \le 10^9$，$0 \le f_i \le c_i$），分别表示经过第 $i$ 条边的流量值和该边的容量。

这些数据应构成一个合法的最大流。此外，恰好有 $k$ 条边满足 $f_i = c_i$。同时，$f_i > 0$ 当且仅当 $g_i = 1$。

若存在多个可行解，输出任意一个即可。

The illustration for second sample case. The saturated edges are marked dark, while edges with g__i = 0 are marked with dotted line. The integer on edge is the index of this edge in input list.

第二个样例的示意图。饱和边以深色标记，而满足 $g_i = 0$ 的边以虚线标记。边上的整数表示该边在输入列表中的索引。