English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
## Note
<center>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. 
</center>
给定一个有向图，包含 #cf_span[n] 个顶点和 #cf_span[m] 条边。顶点 #cf_span[s] 和 #cf_span[t] 分别被标记为源点和汇点。此外，没有边指向 #cf_span[s]，也没有边从 #cf_span[t] 出发。
该图的构造方式如下：最初每条边都有容量 #cf_span[ci > 0]。在该流网络中构造了一个从源点 #cf_span[s] 到汇点 #cf_span[t] 的最大流。记 #cf_span[fi] 为经过第 #cf_span[i] 条边的流量值。随后，所有容量 #cf_span[ci] 和流量值 #cf_span[fi] 均被擦除，取而代之的是在边上标注了指示器 #cf_span[gi] —— 若经过边 #cf_span[i] 的流量为正，即 #cf_span[fi > 0] 时，#cf_span[gi] 为 #cf_span[1]，否则为 #cf_span[0]。
利用该图和 #cf_span[gi] 的值，求出在初始流网络中可能的最小饱和边数（即流量等于容量，满足 #cf_span[fi = ci]）。同时构造一个包含最大流的对应流网络。
有向图中的流由每条边上的流量值 #cf_span[fi] 描述，满足以下条件：
当从源点出发的边的流量总和与指向源点的边的流量总和（本题中不存在此类边）之差最大时，该流为最大流。
输入数据的第一行包含四个正整数 #cf_span[n, m, s, t] (#cf_span[2 ≤ n ≤ 100], #cf_span[1 ≤ m ≤ 1000], #cf_span[1 ≤ s, t ≤ n], #cf_span[s ≠ t]) —— 分别表示顶点数、边数、源点编号和汇点编号。
接下来的 #cf_span[m] 行，每行包含三个非负整数 #cf_span[ui], #cf_span[vi], #cf_span[gi] (#cf_span[1 ≤ ui, vi ≤ n]) —— 分别表示第 #cf_span[i] 条边的起点、终点和指示器，当经过该边的流量为正时 #cf_span[gi] 为 #cf_span[1]，否则为 #cf_span[0]。
保证没有边连接顶点到自身，且每对有序顶点之间至多有一条边，并且至少存在一个满足输入约束的网络流。
第一行输出一个非负整数 #cf_span[k] —— 最大流中必须饱和的最少边数。
接下来的 #cf_span[m] 行，每行输出两个整数 #cf_span[fi, ci] (#cf_span[1 ≤ ci ≤ 109], #cf_span[0 ≤ fi ≤ ci]) —— 分别表示经过第 #cf_span[i] 条边的流量值和该边的容量。
这些数据必须构成一个合法的最大流网络。其中必须恰好有 #cf_span[k] 条边满足 #cf_span[fi = ci]，且 #cf_span[fi > 0] 当且仅当 #cf_span[gi = 1]。
若存在多个可能的答案，输出任意一个即可。
第二个样例的示意图。饱和边用深色标记，而 #cf_span[gi = 0] 的边用虚线标记。边上的整数表示该边在输入列表中的序号。
## Input
输入数据的第一行包含四个正整数 #cf_span[n, m, s, t] (#cf_span[2 ≤ n ≤ 100], #cf_span[1 ≤ m ≤ 1000], #cf_span[1 ≤ s, t ≤ n], #cf_span[s ≠ t]) —— 分别表示顶点数、边数、源点编号和汇点编号。接下来的 #cf_span[m] 行，每行包含三个非负整数 #cf_span[ui], #cf_span[vi], #cf_span[gi] (#cf_span[1 ≤ ui, vi ≤ n]) —— 分别表示第 #cf_span[i] 条边的起点、终点和指示器，当经过该边的流量为正时 #cf_span[gi] 为 #cf_span[1]，否则为 #cf_span[0]。保证没有边连接顶点到自身，且每对有序顶点之间至多有一条边，并且至少存在一个满足输入约束的网络流。
## Output
第一行输出一个非负整数 #cf_span[k] —— 最大流中必须饱和的最少边数。接下来的 #cf_span[m] 行，每行输出两个整数 #cf_span[fi, ci] (#cf_span[1 ≤ ci ≤ 109], #cf_span[0 ≤ fi ≤ ci]) —— 分别表示经过第 #cf_span[i] 条边的流量值和该边的容量。这些数据必须构成一个合法的最大流网络。其中必须恰好有 #cf_span[k] 条边满足 #cf_span[fi = ci]，且 #cf_span[fi > 0] 当且仅当 #cf_span[gi = 1]。若存在多个可能的答案，输出任意一个即可。
[samples]
## Note
第二个样例的示意图。饱和边用深色标记，而 #cf_span[gi = 0] 的边用虚线标记。边上的整数表示该边在输入列表中的序号。
**Definitions**
Let $ G = (V, E) $ be a directed graph with:
- $ V = \{1, 2, \dots, n\} $: set of vertices,
- $ E = \{e_1, e_2, \dots, e_m\} $: set of directed edges, where $ e_i = (u_i, v_i) $,
- $ s \in V $: source vertex,
- $ t \in V $: sink vertex,
- $ g_i \in \{0, 1\} $: indicator for edge $ e_i $, where $ g_i = 1 $ iff flow $ f_i > 0 $.
Let $ f_i \in \mathbb{R}_{\geq 0} $: flow on edge $ e_i $,
Let $ c_i \in \mathbb{R}_{> 0} $: capacity on edge $ e_i $.
**Constraints**
1. $ f_i = 0 $ if and only if $ g_i = 0 $; $ f_i > 0 $ if and only if $ g_i = 1 $.
2. Flow conservation: $ \sum_{e_i \in \text{in}(v)} f_i = \sum_{e_i \in \text{out}(v)} f_i $ for all $ v \in V \setminus \{s, t\} $.
3. $ 0 \leq f_i \leq c_i $ for all $ i \in \{1, \dots, m\} $.
4. No incoming edges to $ s $: $ \text{in}(s) = \emptyset $.
5. No outgoing edges from $ t $: $ \text{out}(t) = \emptyset $.
6. The flow $ \{f_i\} $ is a maximum flow from $ s $ to $ t $.
7. $ c_i \geq f_i > 0 $ for all $ i $ with $ g_i = 1 $; $ c_i > 0 $ for all $ i $, $ c_i $ arbitrary for $ g_i = 0 $ (but $ f_i = 0 $).
**Objective**
Minimize the number of saturated edges:
$$
k = \left| \left\{ i \in \{1, \dots, m\} \mid f_i = c_i \right\} \right|
$$
and construct feasible $ \{f_i\}, \{c_i\} $ achieving this minimum $ k $, satisfying all constraints above.
API Response (JSON)
{
"problem": {
"name": "E. Maximum Flow",
"description": {
"content": "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 the",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF843E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 the...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "给定一个有向图，包含 #cf_span[n] 个顶点和 #cf_span[m] 条边。顶点 #cf_span[s] 和 #cf_span[t] 分别被标记为源点和汇点。此外，没有边指向 #cf_span[s]，也没有边从 #cf_span[t] 出发。\n\n该图的构造方式如下：最初每条边都有容量 #cf_span[ci > 0]。在该流网络中构造了一个从源点 #cf_span[s] 到汇点 #cf_...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ G = (V, E) $ be a directed graph with: \n- $ V = \\{1, 2, \\dots, n\\} $: set of vertices, \n- $ E = \\{e_1, e_2, \\dots, e_m\\} $: set of directed edges, where $ e_i = (u_i, v_i) $,...",
"is_translate": false,
"language": "Formal"
}
]
}