这数据似乎有亿点水了。

我们要跑 $S,T$ 的最小割，然后求出两个点集。这一部分我直接降智用两次 dfs 实现，每次走没有被流完的边，结果 AC 了。不过在另外两道裸题上 WA 了。

经过一个晚上的思考，我终于发现，我的算法是有问题的。比如，给你一条边权全部相同的链，跑完最小割之后，其所有边的流量全都会被流完，导致找出的两个点集分别为 $\{S\}$ 和 $\{T\}$，显然错误。

正确的做法，应该是将最后一轮 bfs 中深度大于 $0$（即被访问到）的点放在 $S_1$ 中，将其他点放在 $S_2$ 中。这样才是正确的，并且通过这样的方式我通过了其他裸题。

综上所述，请求加强数据。

4 3
1 2 2
2 3 2
3 4 2
6
1 2
1 3
1 4
2 3
2 4
3 4

错误的

随机化，但也是错误的

正确的

PS：由于可能会随机化找了两个点，所以上述数据有一定概率卡不掉我的做法。所以上述数据只是一个例子而已，真要卡掉的话，建议造一个长度顶天的边权全部相同的链。或者不失一般性的话，可以去把《不同的最小割》该题中我 WA 的三组数据给挖出来放到这题上并扩大数据范围。