跳到主要内容

P8604 [蓝桥杯 2013 国 C] 危险系数

[蓝桥杯 2013 国 C] 危险系数 P8604​

地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。

我们来定义一个危险系数 DF(x,y)DF(x,y)：

对于两个站点 xx 和 y(x≠y),y(x\neq y), 如果能找到一个站点 zz，当 zz 被敌人破坏后，xx 和 yy 不连通，那么我们称 zz 为关于 x,yx,y 的关键点。相应的，对于任意一对站点 xx 和 yy，危险系数 DF(x,y)DF(x,y) 就表示为这两点之间的关键点个数。

本题的任务是：已知网络结构，求两站点之间的危险系数。

输入数据格式​

输入数据第一行包含 22 个整数 n(2≤n≤1000)n(2 \le n \le 1000)，m(0≤m≤2000)m(0 \le m \le 2000)，分别代表站点数，通道数。

接下来 mm 行，每行两个整数 u,v(1≤u,v≤n,u≠v)u,v(1 \le u,v \le n,u\neq v) 代表一条通道。

最后 11 行，两个数 u,vu,v，代表询问两点之间的危险系数 DF(u,v)DF(u,v)。

输出数据格式​

一个整数，如果询问的两点不连通则输出 −1-1。

输入输出样例​

输入 #1输出 #1
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6		2

说明与提示​

时限 1 秒, 64M。蓝桥杯 2013 年第四届国赛

*练习笔记​

暂无人完成练习，做第一个完成练习的人—-first blood ！