# Smallest Minimum Cut

Time Limit: 2000/2000 MS (Java/Others)

Memory Limit: 65535/32768 K (Java/Others)

## Description

Consider a network $G=(V,E)$ with source $s$ and sink $t$. An s-t cut is a partition of nodes set $V$ into two parts such that $s$ and $t$ belong to different parts. The cut set is the subset of $E$ with all edges connecting nodes in different parts. A minimum cut is the one whose cut set has the minimum summation of capacities. The size of a cut is the number of edges in the cut set. Please calculate the smallest size of all minimum cuts.

## Input

The input contains several test cases and the first line is the total number of cases $T~(1\le T\le 300)$.
Each case describes a network $G$, and the first line contains two integers $n~(2\le n\le 200)$ and $m~(0\le m\le 1000)$ indicating the sizes of nodes and edges. All nodes in the network are labelled from $1$ to $n$.
The second line contains two different integers $s$ and $t~(1\le s,t\le n)$ corresponding to the source and sink.
Each of the next $m$ lines contains three integers $u,v$ and $w~(1\le w\le 255)$ describing a directed edge from node $u$ to $v$ with capacity $w$.

## Output

For each test case, output the smallest size of all minimum cuts in a line.

## Sample Input

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

## Sample Output

2
3

liuyiding

## Source

2017 ACM/ICPC Asia Regional Qingdao Online