题目描述(ID:12380)
标题: 封锁道路
标签:
详情: 春天快到了,林克又蠢蠢欲动。
啊哈沃德收到消息,某地发生了叛乱。啊哈沃德立刻作出反应,派出军队前去镇压叛乱。由于命令十分突然,只有一支队伍做好了即刻出发的准备。 叛军得知后开始向周围扩散。为了保证星球居民不受伤害,他决定派出一支队伍派去封锁一条道路,保护城镇。
现在给定战乱区的 n 个城镇,城镇间共有 m 条边将各个城镇连接起来。请求出在只能封锁一条道路的情况下,最多可以保证多少个城镇一定不会被叛军侵扰。
输入格式:
第一行给定三个整数 n,m 和 k。n 个城镇,m 条道路(双向道路),k 表示第 k 个城镇发生了叛乱。接下来给出 m 行,每行两个正整数表示这两个城镇之间有边相连。
输出格式:
一个整数,表示最多可以保证几个城镇不受侵扰。
限制: 30%的数据 1<=n<=100 1<=m<=200
50%的数据 1<=n<=1000 1<=m<=2000
100%的数据 1<=n<=100,000 1<=m<=200,000
城镇编号从 1 开始,且编号连续,所有城镇全部联通。
样例:

输入

15 15 1
1 2
2 3
3 4
2 4
1 5
5 6
6 7
7 5
6 8
8 9
1 10
10 11
11 12
12 13
13 14

输出

5

解释

封锁 1-5 这条边,可以使得 5、6、7、8、9 五个城镇不被侵扰
或者封锁 1-10 这条边,也可以使得 10、11、12、13、14 五个城镇不被侵扰

输入

13 14 3
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 8
8 9
2 10
10 11
11 13
13 12
12 10

输出

5

解释

封锁 1-5 这条边,可以使得 5、6、7、8、9 五个城镇不被侵扰。
登录并解答