30085 - B城

B 城有 n 个城镇,m 条双向道路。

每条道路连结两个不同的城镇,没有重复的道路,所有城镇连通。

把城镇看作节点,把道路看作边,容易发现,整个城市构成了一个无向图。

现在,对于每个节点 i,把与节点 i 关联的所有边去掉以后(不去掉节点 i 本身),需要统计无向图中有多少个有序点对 (x, y),满足 xy 不连通。

输入

第一行包含两个整数 nm

接下来 m 行,每行包含两个整数 ab,表示城镇 ab 之间存在一条道路。

输出

输出共 n 行,每行输出一个整数。

i 行输出的整数表示把与节点 i 关联的所有边去掉以后,无向图中有多少个有序点对 (x, y),满足 xy 不连通。

样例

输入

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

输出

8
8
16
14
8

提示

  • n \le 100000
  • m \le 500000
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题