# Problem G

Minimum Cut

Given a directed weighted graph and two vertices $s$, $t$, the goal is to find a subset $U$ of the vertices such that $s \in U$, $t \not\in U$, and the weight of edges from $U$ to $\overline{U}$ is minimized.

## Input

The first line of input contains four non-negative integers, $2 \le n \le 500$, $0 \le m \le 10\, 000$, $0 \le s \le n-1$ and $0 \le t \le n-1$, separated by single spaces, where $n$ is the numbers of nodes in the graph, $m$ is the number of edges, $s$ is the source and $t$ is the sink ($s \ne t$). Nodes are numbered from $0$ to $n-1$. Then follow $m$ lines, each line consisting of three (space-separated) integers $u$, $v$ and $w$ indicating that there is an edge from $u$ to $v$ in the graph with weight $1 \le w \le 10^8$.

## Output

Output should begin with a line containing an integer $k$, giving the size of $U$. Then follow $k$ lines giving the vertices in $U$, one per line. If there are multiple choices for $U$ any one will be accepted.

You may assume that there is a cut such that the total weight of edges from $U$ to $\overline{U}$ is less than $2^{31}$.

Sample Input 1 | Sample Output 1 |
---|---|

4 5 0 3 0 1 10 1 2 1 1 3 1 0 2 1 2 3 10 |
2 1 0 |

Sample Input 2 | Sample Output 2 |
---|---|

2 1 0 1 0 1 100000 |
1 0 |

Sample Input 3 | Sample Output 3 |
---|---|

2 1 1 0 0 1 100000 |
1 1 |