题目描述

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

拜托西亚有 $n$ 座城市，城市间由双向道路连接，形成一个连通图（任意两城市可互相到达）。每座城市有一位居民，总计需进行 $n \times (n-1)$ 次会面（每人访问其他人一次）。若封锁某座城市（禁止进入、离开、通过），会导致无法在该城市两侧的城市间进行会面。需计算封锁每座城市时，无法进行的会面次数。

输入格式

1. 第一行：两个整数 $n, m$（$2 \leq n \leq 10^5$，$1 \leq m \leq 5 \times 10^5$），分别表示城市数和道路数；
2. 接下来 $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