#8743. 「一本通 3.6 练习 5」Blockade
「一本通 3.6 练习 5」Blockade
题目描述
原题来自:POI 2008 Stage 2
Byteotia 有 个城镇。一些城镇之间有双向道路连接。尽管可能有桥,隧道或者立交,但城外没有交叉路。每对城镇最多被一条道路连接。一个人可以从任意一个城镇到达任意另一个城镇——直接或间接地。
每个城镇都有恰好一个居民。因此居民们十分孤独。事实上,每个居民都想(在对方居民所住的地方)拜访其他任意一个居民,并且拜访恰好一次。所以应当恰好会进行 次拜访。不幸的是,要求立刻为自己开发的程序付钱的程序员总罢工正在进行。作为抗议的一个措施,程序员们计划封锁 Byteotia 的一个城镇,阻止人进入,离开甚至通过这个城镇。正在我们说话的时候,他们正在争论选择哪个城镇才能导致最严重的后果。
写一个程序,从标准输入读取 Byteotia 的路网,输出对于每个确定的城镇,如果程序员们封锁了这个城镇,将有多少次拜访不能进行?
一句话题意
Byteotia 城市有 个城镇, 条双向道路。每条道路连接两个不同的城镇,没有重复的道路,所有城镇连通。
输出 个数,代表如果把与第 个点连接的所有边去掉,将有多少对有序点对不能互通。
输入格式
输入 及 条边。
输出格式
输出 个数,代表如果把第 个点连接的所有边去掉,将有多少对有序点不能互通。
样例
5 5
1 2
2 3
1 3
3 4
4 5
8
8
16
14
8
数据范围与提示
。