9227: 危险系数

内存限制:64 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

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

输入格式

输入数据第一行包含 $2$ 个整数 $n(2 \le n \le 1000)$,$m(0 \le m \le 2000)$,分别代表站点数,通道数。 接下来 $m$ 行,每行两个整数 $u,v(1 \le u,v \le n,u\neq v)$ 代表一条通道。 最后 $1$ 行,两个数 $u,v$,代表询问两点之间的危险系数 $DF(u,v)$。

输出格式

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

输入样例 复制

7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6

输出样例 复制

2

数据范围与提示

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