Count of Shortest Paths in an Unweighted Graph

You are given an undirected and unweighted graph with N vertices and M edges. The vertices are numbered from 1 to N. Your task is to determine the number of shortest paths from vertex 1 to every other vertex in the graph.

More formally, for each vertex i (1 ≤ i ≤ N), compute the number of distinct shortest paths from vertex 1 to vertex i.
If a vertex is unreachable from vertex 1, the number of shortest paths to that vertex should be 0.

The distance between two vertices is defined as the minimum number of edges in any path connecting them.

Note: The formulas used in this problem are in LaTeX format. For example, the number of vertices is given by \(N\) and the number of edges by \(M\).

inputFormat

The first line contains two integers \(N\) and \(M\) — the number of vertices and edges respectively.

Each of the following \(M\) lines contains two integers \(u\) and \(v\) indicating that there is an undirected edge between vertices \(u\) and \(v\).

\(1 \leq u, v \leq N\)

outputFormat

Output a single line with \(N\) integers separated by spaces. The \(i^{th}\) integer should represent the number of shortest paths from vertex 1 to vertex \(i\).

sample

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

1 1 1 2