STC10 - Blockade


## 题目描述 $Byteotia$ 城市有 $n$ 个城镇,$ m $ 条双向道路。每条道路连接两个不同的城镇,没有重复的道路,所有城镇连通。现在要你求出当封闭第 $i$ 个城镇有多少个本质不同$($即$(1,2)$与$(2,1)$不同$)$的城镇对不能连通。 ## 输入输出格式 ### 输入格式: 输入 $n$, $m,$ 分别代表 $n$ 个城镇, $m$ 条双向道路。 接下来 $m$ 行,每一行输入 $u$ ,$v$ 表示城镇$u$ 与城镇 $v$ 之间有一条双向道路。 ### 输出格式: 输出 $n$ 行,每行一个数,代表第 $i$ 个城镇封闭后,有多少个本质不同的城镇对不能连通。 ### 输入输出样例: ###### 输入样例#1: ```cpp 5 5 1 2 2 3 1 3 3 4 4 5 ``` ###### 输出样例#1: ```cpp 8 8 16 14 8 ```


There are exactly N towns in Byteotia. Some towns are connected by bidirectional roads. There are no crossroads outside towns, though there may be bridges, tunnels and flyovers. Each pair of towns may be connected by at most one direct road. One can get from any town to any other-directly or indirectly. Each town has exactly one citizen. For that reason the citizens suffer from loneliness. It turns out that each citizen would like to pay a visit to every other citizen (in his host's hometown), and do it exactly once. So exactly N\*(N-1) visits should take place. That's right, _should_. Unfortunately, a general strike of programmers, who demand an emergency purchase of software, is under way. As an act of protest, the programmers plan to block one town of Byteotia, preventing entering it, leaving it, and even passing through. As we speak, they are debating which town to choose so that the consequences are most severe. Task ---- Write a programme that: - reads the Byteotian road system's description from the standard input, - for each town determines, how many visits could take place if this town were not blocked by programmers, - writes out the outcome to the standard output. Input ----- In the first line of the standard input there are two positive integers: N and N (1 <= N <= 100000, 1 <= M <= 500000) denoting the number of towns and roads, respectively. The towns are numbered from 1 to N. The following M lines contain descriptions of the roads. Each line contains two integers X $ _{i} $ and Y $ _{i} $ (1 <= X $ _{i} $ , Y $ _{i} $ <= N) and denotes a direct road between towns numbered X $ _{i} $ and Y $ _{i} $ . Output ------ Your programme should write out exactly N integers to the standard output, one number per line. The i-th line should contain the number of visits that could not take place if the programmers blocked the town no. i. Example ------- For the input data: ``` 5 5 1 2 2 3 1 3 3 4 4 5 ``` the correct result is: ``` 8 8 16 14 8 ```