#1822. 「一本通 3.6 练习 5」Blockade

「一本通 3.6 练习 5」Blockade

题目描述

原题来自:POI 2008 Stage 2

Byteotia 有 nn 个城镇。一些城镇之间有双向道路连接。尽管可能有桥,隧道或者立交,但城外没有交叉路。每对城镇最多被一条道路连接。一个人可以从任意一个城镇到达任意另一个城镇——直接或间接地。

每个城镇都有恰好一个居民。因此居民们十分孤独。事实上,每个居民都想(在对方居民所住的地方)拜访其他任意一个居民,并且拜访恰好一次。所以应当恰好会进行 n(n1)n\cdot (n-1) 次拜访。不幸的是,要求立刻为自己开发的程序付钱的程序员总罢工正在进行。作为抗议的一个措施,程序员们计划封锁 Byteotia 的一个城镇,阻止人进入,离开甚至通过这个城镇。正在我们说话的时候,他们正在争论选择哪个城镇才能导致最严重的后果。

写一个程序,从标准输入读取 Byteotia 的路网,输出对于每个确定的城镇,如果程序员们封锁了这个城镇,将有多少次拜访不能进行?


一句话题意

Byteotia 城市有 nn 个城镇,mm 条双向道路。每条道路连接两个不同的城镇,没有重复的道路,所有城镇连通。
输出 nn 个数,代表如果把与第 ii 个点连接的所有边去掉,将有多少对有序点对不能互通。

输入格式

输入 n,mn,mmm 条边。

输出格式

输出 nn 个数,代表如果把第 ii 个点连接的所有边去掉,将有多少对有序点不能互通。

样例

5 5
1 2
2 3
1 3
3 4
4 5
8
8
16
14
8

blo

数据范围与提示

n105,m5×105n\le 10^5, m\le 5\times 10^5