Problem A
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}$.

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