All Pairs Shortest Path in an Undirected Graph

Given an undirected graph with \(n\) vertices and \(m\) edges, compute the shortest path between every pair of vertices \((i, j)\). Two vertices are connected if there exists a path between them and the distance is defined as the minimum number of edges used. If no path exists between two vertices, output \(-1\) for that pair.

Note: The vertices are numbered from 1 to \(n\). The graph does not contain self-loops or multiple edges.

inputFormat

The first line contains two integers \(n\) and \(m\). Each of the next \(m\) lines contains two integers \(u\) and \(v\) denoting an undirected edge between vertices \(u\) and \(v\).

outputFormat

Output an \(n \times n\) matrix. The element in the \(i\)th row and \(j\)th column should be the length of the shortest path from vertex \(i\) to vertex \(j\). If there is no path, output \(-1\) for that entry. Separate numbers in the same row by a single space, and output each row on a new line.

sample

4 4
1 2
2 3
3 4
1 4

0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0