← 返回题目
题库练习 战略要地
← 上一题 下一题 →

A71424 | 战略要地

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

A 国有 n 个城市（城市编号为 1 \sim n ），城市间建有 m 条双向的道路。

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

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

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

输入格式

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

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

最后 1 行，输入 2 个整数 t_1 ， t_2 ，含义如题所述。（t_1 \neq t_2）

输出格式

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

输入输出样例

输入 #1
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
输出 #1
2
输入 #2
8 9
1 2
2 3
2 4
3 4
4 5
5 6
5 7
6 7
7 8
1 8
输出 #2
4
输入 #3
5 4
1 2
2 3
2 4
3 4
1 5
输出 #3
-1
C++ 编辑器
输入
输出