Minimum Cut

Problem Source

AHOI 2009

Problem Description

Countries A and B are at war. In country A's material transport network there are $N$ transit stations and $M$ one-way roads. Suppose the $i$-th road ($1 \leq i \leq M$) connects transit stations $v_i$ and $u_i$; then transit station $v_i$ can reach transit station $u_i$ via this road, and cutting this road costs $c_i$.

Now country B wants to find a set of roads to cut so that transit station $s$ can no longer reach transit station $t$, while minimizing the total cutting cost.

Little Cocoa immediately saw that this is a minimum-cut problem. But the thoughtful Little Cocoa is not satisfied with just that. For each one-way road he now raises two questions:

• Question 1: Is there a minimum-cost cutting plan in which this road is cut?
• Question 2: Is this road cut in every minimum-cost cutting plan?

Please answer these two questions for each road.

Input Format

The first line contains four positive integers $N, M, s, t$ ($N \leq 4000,\ M \leq 60000$).

Lines $2$ to $M+1$ each contain three positive integers $v, u, c$, indicating a one-way road from transit station $v$ to transit station $u$ with cutting cost $c$ ($1 \leq c \leq 100000$).

Note: there may be multiple roads directly connecting the same pair of transit stations.

Output Format

For each one-way road, in the order they were input, output one line containing two integers that are each either $0$ or $1$, representing the answers to question 1 and question 2 respectively ($1$ means yes, $0$ means no).

Sample Input

6 7 1 6
1 2 3
1 3 2
2 4 4
2 5 1
3 5 5
4 6 2
5 6 3

Sample Output

1 0
1 0
0 0
1 0
0 0
1 0
1 0

Hint

Let the edge from the $(i+1)$-th input line be edge $i$. Then $\{1, 2\}, \{6, 7\}, \{2, 4, 6\}$ are the only three minimum-cost cutting plans. Their union is $\{1, 2, 4, 6, 7\}$, and their intersection is $\{\varnothing\}$.