2517 - 战略要地

题目描述

A 国有 n 个城市(城市编号为 1 \sim n ),城市间建有 m 条双向的道路。

该国战争爆发后,国防部长下令要重点保护 t_1t_2 这两个城市,且为了保障这两个城市之间的运输保障,要计算出两个城市之间有哪些战略保障城市。

战略保障城市的意思是说,如果某城市 x 被敌人攻下了,那么 t_1t_2 就无法实现运输,也就是两个城市之间通过任何路线都不能互相到达。(x \neq t_1,x \neq t_2

请编程计算出,该国有几个战略保障城市。

输入

1 行输入 nm ,含义如题所述。(2 \le n \le 1000), (0 \le m \le 2000)

接下来 m 行,每行有 2 个整数 xyx \neq y),代表这两个城市之间修建了一条双向道路。

最后 1 行,输入 2 个整数 t_1t_2 ,含义如题所述。(t_1 \neq t_2

输出

输出一个整数,代表战略保障城市的数量,如果两个城市本来就不连通,请输出 -1

样例

输入

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

输出

2

输入

8 9
1 2
2 3
2 4
3 4
4 5
5 6
5 7
6 7
7 8
1 8

输出

4

输入

5 4
1 2
2 3
2 4
3 4
1 5

输出

-1
来源

东方博宜OJ

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 136
通过人数 59
金币数量 2 枚
难度 基础


上一题 下一题