Computing Structural Hole Values in Social Networks

In a social network represented by an undirected graph \(G=(V,E)\), the structural hole value of a vertex \(v_i\) is defined based on its neighbors. Let \(N(v_i)\) denote the set of neighbors of \(v_i\). For any two distinct neighbors \(v_j\) and \(v_k\), define:

\[ span_i(j,k) = \text{the shortest distance between } v_j \text{ and } v_k \text{ in } G\setminus\{v_i\} \quad (\text{i.e., with all edges incident on } v_i \text{ removed}) \]

and let \(dist(j,k)\) be the shortest distance between \(v_j\) and \(v_k\) in the original graph \(G\). Then the structural hole value of vertex \(v_i\) is defined as:

[ sh_i = \sum_{\substack{v_j,v_k \in N(v_i)\ j\neq k}}\Bigl(span_i(j,k)-dist(j,k)\Bigr) ]

Your task is to compute \(sh_i\) for every vertex \(v_i\) in the social network. It is guaranteed that the given graph is 2-connected, so that for every vertex \(v_i\), the induced graph after removing \(v_i\) remains connected among its neighbors.

Note: Vertices are numbered from 1 to \(n\). Use Breadth First Search (BFS) to compute shortest paths. In the computation, if a pair of neighbors is present, consider each unordered pair only once.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of vertices and the number of edges in the social network.

Each of the following \(m\) lines contains two integers \(u\) and \(v\) denoting an undirected edge between vertices \(u\) and \(v\).

The input graph is guaranteed to be 2-connected.

outputFormat

Output \(n\) lines. The \(i\)-th line should contain a single integer denoting the structural hole value \(sh_i\) for vertex \(v_i\).

sample

4 4
1 2
2 3
3 4
4 1

0
0
0
0