A71424. 战略要地
编程题
基础
知识点
题目描述
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