#P2545. 危险系数

危险系数

题目背景

抗日战争时期,冀中平原的地道战曾发挥重要作用。

题目描述

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

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

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

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

输入格式

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

接下来 mm 行,每行两个整数 u,v(1u,vn,uv)u,v(1 \leq u,v \leq n, u \neq v) 代表一条通道。

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

输出格式

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

样例

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

说明

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