Problem : 68 - 征服者

Problem Statistics

Solved Member: 27　　Submission: 141　　User Tried: 28

Statement:

兔子王國準備要入侵銀河系，首先，他希望能癱瘓銀河系的交通系統。

整個銀河系是由 N 個由 1 編號到 N 的星球以及 M 條雙向的道路所連接而成，兩個固定的星球之間最多只會有一條路直接連接，並且所有的星球最初皆可以透過有線條道路互相往來。
星球間依照起點以及終點分類存在著 N(N-1) 種有向的路線，每條路線都可以經過數條道路由其中一個星球走到另一個不同的星球。

兔王已經決定用一顆核彈來破壞其中一顆星球，請你幫他分析，每個星球破壞之後會使幾個點對癱瘓。
若要使(i,j)點對癱瘓，代表不存在任何一條路徑可以從 i 星走到 j 星。

Input:Output:

第 1 行有兩個整數 N(1 ≤ N ≤ 100000),M(1 ≤ M ≤ 500000)，代表星球數量以及道路數量。
後面 M 行每行有兩個數字 A,B，代表有一條道路直接連接 A,B 兩星球。

請輸出 N 行，每行一個數字。
第 i 行的數字代表破壞星球 i 可以使幾個點對癱瘓。

Sample Input:Sample Output:

5 5
1 2
2 3
1 3
3 4
4 5

8
8
16
14
8

HINT:

以破壞星球 4 來說，會使得 14 個點對癱瘓：
(1,4)、(4,1)
(2,4)、(4,2)
(3,4)、(4,3)
(5,4)、(4,5)
(1,5)、(5,1)
(2,5)、(5,2)
(3,5)、(5,3)
其中(i,j)代表以 i 為起點，j 為終點的路線。

Source:

POI 15 Stage 2

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	32768kb
1-ocen	1000ms	32768kb
1	1000ms	32768kb	10
2-ocen	1000ms	32768kb
2	1000ms	32768kb	10
3-ocen	1000ms	32768kb
3	1000ms	32768kb	10
4-ocen	1000ms	32768kb
4	1000ms	32768kb	10
5-ocen	5000ms	32768kb
5	1000ms	32768kb	10
6	1000ms	32768kb	10
7	2000ms	32768kb	10
8	2000ms	32768kb	10
9	3000ms	32768kb	10
10	3000ms	32768kb	10