题目描述
给出一个无向图,求在该图中任意两点之间,最少经过几条边可以到达
图中可能存在重边(即连接同一对顶点的两条及以上的边)和自环(即连接某个点和它自身的边)
输入描述
输入的第一行为2个正整数n,m。分别表示给出的图的顶点数和边数。(1 <= n <= 200, 1 <= m <= n*(n-1)/2 )
接下来m行,每行两个正整数x,y。表示一条边的两个顶点编号。(顶点编号从1到n)
输出描述
输出包含n行,每行包含n个数,第i行第j个数表示从顶点i到顶点j,最少经过几条边可以到达,如果不可达,则输出-1
样例输入
5 3
1 2
2 3
4 5
样例输出
0 1 2 -1 -1
1 0 1 -1 -1
2 1 0 -1 -1
-1 -1 -1 0 1
-1 -1 -1 1 0
提示
分别以每个点为起点,调用一次bfs即可