Problem E
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\notin U$, and the weight of edges from $U$ to $\bar{U}$ is minimized.

Input

The first line of input contains four non-negative integers, $2\le n\le 500$, $0\le m\le 10000$, $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 $\bar{U}$ is less than $2^{31}$.

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

2
1
0

2 1 0 1
0 1 100000

1
0

2 1 1 0
0 1 100000

1
1