题目描述

Byteotia 有 $n$ 个城镇和 $m$ 条双向道路，任意两个城镇之间都可以互相到达。每个城镇恰好有一名居民，每名居民都希望前往其他每个城镇各访问一次，因此原本共有 $n(n-1)$ 次访问。

现在要封锁其中一个城镇。被封锁的城镇不能进入、离开或经过。对于每个城镇，请计算封锁该城镇后，有多少次访问无法完成。

访问的起点和终点不同，且访问是有方向的。例如，从城镇 $1$ 到城镇 $2$ 与从城镇 $2$ 到城镇 $1$ 是两次不同的访问。

输入格式

第一行包含两个整数 $n,m$，分别表示城镇数和道路数。

接下来 $m$ 行，每行包含两个整数 $a,b$，表示城镇 $a$ 与城镇 $b$ 之间有一条双向道路。

输出格式

输出 $n$ 行，第 $i$ 行包含一个整数，表示封锁城镇 $i$ 后无法完成的访问次数。

样例

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

8
8
16
14
8

数据范围与提示

• $1 \le n \le 10^5$
• $1 \le m \le 5 \times 10^5$
• 图中没有自环和重边，并且整个图连通。

来源

一本通 3.6 练习 5，POI 2008