P12064 [THOI 2012] 社交网络结构洞

搬运自 [2012 年清华大学信息学邀请赛](https://gitlink.org.cn/thusaa/thoi2012)。

近日，社交网络研究的鼻祖 Jon Kleinberg 教授在清华大学给同学们带来了一个关于社交网络结构洞（Structural Hole）的主题演讲。对社交网络有着浓厚兴趣的小 W 也旁听了这次演讲。在演讲中 Jon Kleinberg 教授讲到社交网络结构洞是描述一个人在一个社交网络中重要程度的一个指标，那么如何定量地分析每一个人在社交网络的重要程度呢？ 小 W 阅读很多参考文献，发现有一种通过计算社会关系跨度的方法。 - **【定义】社交网络**：用 $G=(V,E)$ 表示一个社交网络，其中 $V$ 是网络中人的集合，$E\subseteq V\times V$ 是人与人之间的关系集合。 - **【定义】社交网络距离**：$v_i$ 和 $v_j$ 两个人的社交网络距离 $dist_{i,j}$ 为 $v_i$ 和 $v_j$ 之间的最短距离。 - **【定义】社会关系跨度**：用 $span_k(i,j)$ 表示，是在社交网络中去掉所有与 $v_k$ 相关的边（即边的一个端点为 $v_k$）之后 $v_i$ 和 $v_j$ 之间的最短距离。 那么描述每一个人的结构洞值 $sh_i$ 表示其所有邻居节点之间社会关系跨度与社交网络距离差值的和。 $$sh_i=\sum\limits_{v_j,v_k\in N(v_i),j\neq k}(span_i(j,k)-dist_{j,k})$$ 其中 $N(v_i)$ 表示 $v_i$ 的邻居节点集合。 由于社交网络中人的数量十分庞大，计算每个人的结构洞值也变得十分困难。小 W 想请你帮助设计出一种好的计算方法，求出社交网络中所有人的结构洞值。

输入的第一行包含两个整数 $n,m$，表示社交网络中人的数量（人从 $1$ 到 $n$ 编号）和关系的数量。 接下来 $m$ 行描述人们的关系情况，其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1\le a_i,b_i\le n$），表示 $a_i$ 和 $b_i$ 两个人之间在社交网络中有直接关系。

输出一共 $n$ 行，每行一个整数，表示每个人在社交网络中的结构洞值。

### 【对样例的说明】 样例输入中的社交网络如下图所示：  $v_3$ 的结构洞值是 $1$，因为 $v_1$ 和 $v_2$ 的距离原本是 $2$，而去掉 $v_3$ 之后变成 $3$。而其他人的结构洞值都是 $0$，因为去掉他们并不会影响他们的邻居之间的距离。 ### 【数据规模与约定】 所有测试数据的范围和特点如下表所示。