Minimum Cut Query Analysis

Countries A and B are at war. Country A has a logistics network consisting of \(N\) intermediate stations and \(M\) directed roads. The \(i\)-th road (\(1 \le i \le M\)) goes from station \(v_i\) to station \(u_i\) and has a cutting (removal) cost \(c_i\). Country B wishes to prevent station \(s\) from reaching station \(t\) by cutting a set of roads such that the total cost is minimized; in other words, they want to find a minimum \(s\)-\(t\) cut.

However, the problem does not stop there. For each directed road, you are also required to answer the following two questions:

• Question 1: Does there exist a minimum cut in which this road is cut?
• Question 2: Is it the case that in every minimum cut this road is cut?

For each road, output two answers (each either YES or NO) corresponding to the questions above.

Note: All mathematical formulas are written in \(\LaTeX\) format. The stations are numbered from 1 to \(N\); thus, \(1 \le s,t \le N\).

inputFormat

The first line contains four integers \(N\), \(M\), \(s\), and \(t\).

Each of the following \(M\) lines contains three integers \(v_i\), \(u_i\), and \(c_i\), indicating a directed road from station \(v_i\) to station \(u_i\) with removal (cutting) cost \(c_i\).

outputFormat

Output \(M\) lines. The \(i\)-th line should contain two words separated by a space:

• The answer for Question 1 for the \(i\)-th road – output YES if there exists a minimum cut in which this road is cut, and NO otherwise.
• The answer for Question 2 for the \(i\)-th road – output YES if in every minimum cut this road is cut, and NO otherwise.

sample

4 5 1 4
1 2 3
2 4 3
1 3 4
3 4 1
2 3 2

YES NO
YES YES
YES NO
YES YES
YES NO