Description

Countries $A, B$ are at war. In country $A$’s supply transport network, there are $N$ transshipment stations and $M$ directed roads. Suppose the $i$-th ($1\le i\le M$) road connects stations $v_i, u_i$, meaning that station $v_i$ can reach station $u_i$ via this road. Cutting this road costs $c_i$.

Country $B$ wants to find a set of roads to cut so that station $s$ cannot reach station $t$, and the total cutting cost is minimized.

Xiao Keke immediately recognizes that this is a minimum cut problem. But the thoughtful Xiao Keke goes further. For each directed road, he asks two questions:

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

Please answer these two questions.

Input Format

The first line contains $4$ positive integers: $N, M, s, t$.

Each of the next $M$ lines contains $3$ positive integers $v, u, c$, indicating a directed road from station $v$ to station $u$, with cutting cost $c$ ($1\le c\le 100000$).

Note: There may be multiple roads directly connecting the same pair of stations. Within the same line, adjacent numbers may be separated by one or more spaces.

Output Format

For each directed road, in the input order, output one line containing two integers, each either $0$ or $1$. They are the answers to Question 1 and Question 2 respectively ($1$ means yes, $0$ means no). Separate the two numbers on the same line with a single space, and do not print extra spaces at the beginning or end of the line.

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

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

Hint

Let the edge given on line $(i+1)$ be labeled as edge $i$. Then $\{1,2\}, \{6,7\}, \{2,4,6\}$ are the only three minimum-cost cuts. Their union is $\{1,2,4,6,7\}$, and their intersection is $\varnothing$.

The scale of the testdata is shown in the table below.

Translated by ChatGPT 5