抗日战争时期,冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接,形成了庞大的网络。但也有隐患,当敌人发现了某个站点后,其它站点间可能因此会失去联系。
我们来定义一个危险系数 $DF(x,y)$:
对于两个站点 $x$ 和 $y(x\neq y),$ 如果能找到一个站点 $z$,当 $z$ 被敌人破坏后,$x$ 和 $y$ 不连通,那么我们称 $z$ 为关于 $x,y$ 的关键点。相应的,对于任意一对站点 $x$ 和 $y$,危险系数 $DF(x,y)$ 就表示为这两点之间的关键点个数。
本题的任务是:已知网络结构,求两站点之间的危险系数。