SP17261 BANKROB - Bank robbery

城市中频繁出现银行抢劫案，去年几乎每周都有一家银行被抢。警方希望解决这一问题，但直接在每家银行安排警力显然不切实际，因为成本太高，而当前的经济状况也不允许这样做。 于是，警方找到了一种替代方案：他们可以在抢劫事件发生后迅速反应。劫匪的逃跑方式只有摩托车或汽车。警方可以封锁城市中的任意一个交叉路口，劫匪试图通过已封锁的路口会被抓住。另外，警方能够预测从某个银行出发的可能逃跑目的地。因此，他们在收到抢劫警报后立即采取行动，堵住一些交叉路口，从而阻止劫匪到达逃逸地点。此外，封锁的路口越少越好，这样不仅可以降低成本，更能提高追捕效率，并减少对市民的影响。 然而，仅计算从某个银行到指定逃逸点之间需要封锁的最少交叉路口数量对警方来说意义不大。由于城市结构的特点，最小封锁集很可能是靠近银行的几个路口，而等到警方到达时，劫匪可能已经逃到其他地方。因此，在追捕过程中，警方需要根据实时情况进行决策。为了做出这种决策，警方需要一个高效的计算机程序来计算最佳封锁方案。你的任务就是编写这个程序：根据输入的城市地图以及两个位置 $s$ 和 $t$，找出从位置 $s$ 到位置 $t$ 的最小封锁交叉路口数量。

程序从标准输入读取数据。第一行输入两个自然数 $n$ 和 $m$（$1 < n \leq 1000, 1 \leq m \leq 5000$），分别表示城市中的交叉路口数量和街道数量。每条街道连接两个交叉路口，任何两个交叉路口之间最多只有一条街道。交叉路口的编号从 $1$ 到 $n$。第二行输入两个数字 $s$ 和 $t$，表示需要切断连接的两个交叉路口。接下来的 $m$ 行，每行包含两个数字 $c_1, c_2$，表示有一条双向街道连接交叉路口 $c_1$ 和 $c_2$。

输出一个数字，表示封锁若干交叉路口后，从位置 $s$ 无法到达位置 $t$ 所需的最少交叉路口数量。可以假定 $s$ 和 $t$ 之间没有直接相连的街道。 **本翻译由 AI 自动生成**