该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile5342.zip](file://AdditionalFile5342.zip?type=additional_file)

#5342. 「POI2008 R2」封锁 Blockade

标签: 传统 | 时间限制: 2000 ms | 内存限制: 32 MiB |

题目描述

题目译自 XV OI Olimpiada Informatyczna – II etap Blokada

拜托西亚共有 $n$ 座城市，部分城市间由双向道路连接。道路仅在城市相交，可能包括桥梁、隧道或高架桥。任意两城市间至多有一条道路。每城市可通过直接或间接路径到达其他城市。

每城市居住一位居民，深受孤独困扰。居民希望每人访问其他每人一次，总计需 $n \cdot (n-1)$ 次会面。然而，拜托西亚正爆发程序员抗议，要求政府紧急收购软件。他们计划封锁一座城市，禁止进入、离开或通过，以最大程度扰乱居民会面。你需确定选择哪座城市封锁会造成最大影响。

编写程序：

• 从标准输入读取拜托西亚道路网络描述。
• 计算每城市封锁时无法进行的会面次数。
• 将结果输出到标准输出。

输入格式

第一行包含两个自然数 $n, m$ $(2 \leq n \leq 100000, 1 \leq m \leq 500000)$，分别表示城市数和道路数。城市从 $1$ 到 $n$ 编号。接下来的 $m$ 行描述道路，每行包含两个整数 $a, b$ $(1 \leq a < b \leq n)$，表示城市 $a$ 和 $b$ 间存在道路。

输出格式

输出 $n$ 行，每行一个自然数。第 $i$ 行表示若程序员封锁城市 $i$，无法进行的会面次数。

样例

输入

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

输出

8
8
16
14
8