预留退路

只有一个入口，太危险了。如果Zero封了它，你们就困死在核心区。

"需要第二条路。"你说。

"挖？"CC问。

"挖不动。"你说，"墙壁是合金的，没工具。"

"那咋办？"

"找已有的路。"你说，"核心区的通风管道、维修通道、废弃电缆井——这些算不算路？"

"算。"Echo说，"但它们太窄，只能爬。"

"能爬就行。"你说，"紧急时候，爬也比死强。"

你把所有能走的路都标在地图上——主通道是红线，通风管是蓝线，电缆井是绿线。红线只有一条，但蓝线和绿线密密麻麻，像一张网。

"这样。"你说，"从入口进，如果被封，走通风管到B点，再爬电缆井到C点，然后从C点的维修通道出去。"

"路太绕。"CC说。

"绕但活。"你说，"我们需要至少两条完全不同的路——不共享任何一段，这样即使一条被封，另一条还能走。"

"边不相交？"

"对。"你说，"这叫'退路'——不是备用，是独立的。"

你开始找。从起点到终点，找两条没有公共边的路径。第一条走主通道，第二条走通风管加电缆井。

"找到了。"你说，"两条路，没有重叠。"

"如果两条都被封呢？"

"那就找第三条。"你说，"总有一条能走。"

"如果所有路都被封？"

你看着她。

"那就打出去。"你说，"但在此之前，我们要把退路准备好。"

CC把退路路线刻在自己的金属手臂上——用刀尖刻的，歪歪扭扭，但清楚。

"刻这干啥子？"

"怕忘。"她说，"紧急时候，脑子会空白。"

"你不会忘。"

"我会。"她说，"所以我刻下来。"

题目描述

给定一张无向图，问从起点 $s$ 到终点 $t$ 有多少条边不相交的路径（即没有公共边）。

输入格式

$n, m, s, t$。然后 $m$ 条边 $(u, v)$。

输出格式

边不相交路径的最大数量。

输入样例

3 2
1 2
2 3

输出样例

1

提示

• Menger定理：边不相交路径的最大数量 = 最小边割的大小。
• 用最大流求解：每条边容量为1，求s-t最大流。
• 也可以用DFS找增广路，统计路径数。

"退路准备好了。"你说。

"三条。"CC数了数，"够多了。"

"不够。"你说，"但只能找到三条。"

"那就三条。"CC说，"总比一条好。"

Echo把退路地图存进服务器——备份了十份，分散在十个节点。

"备份好了。"她说，"就算我没了，地图还在。"

"你不会没。"你说。

"以防万一。"她说。

"没有万一。"你说，"三条退路，十份备份，我们活着出去。"

"对。"Echo说，"活着出去。"

[第六题：破解死局]