Undirected unweighted connected graph is given (no self loops or multiple edges). We have to calculate for each node x number of simple paths with minimum distance from node 1 to node N passing through that node x.

Constraints: N <= 1e3 Number of edges, M <= N * (N-1) / 2