给出一个有n个节点，n 減 1条边的连通图，每条边长均为1。除此之外，现在原图上的每两个不相邻且仅间隔一个节点的节点间建边，边长仍为1。 求对于所有的点对左小括號 u 逗號 v 右小括號，加總 從 空白 到 空白 對 d i s t 左小括號 u 逗號 v 右小括號。其中d i s t 左小括號 u 逗號 v 右小括號指的是左小括號 u 逗號 v 右小括號之间的最短距离。

题目描述：

给出一个有n个节点的连通图，每条边的长度均为1。除此之外，现在在原图上的每两个不相邻且仅间隔一个节点的节点间建立了一个节点。所有新加入的节点两两之间的距离均为1。

对于所有给定的点对左小括号u，v右小括号，加总从空白到空白对dist左小括号u,v右小括号左小括号沿原图边行进的距离加上建立的节点之间路径的长度，左小括号dist左小括号u,v右小括号右小括号表示第u个节点与第v个节点之间的距离。

其中dist左小括号u,v右小括号表示点u到点v的最短路径中边的条数，即点u到点v之间的最短距离。

解题思路：

本题目的是求距离一个节点两个单位距离的两个节点之间的最短路径边数。可以使用广度优先搜索(BFS)求解。

对于每次搜索，先加入点u，将该点u周围一度节点加入队列；对于队列中添加过的元素，说明距离起点的距离为1；对于从队列中取出的元素v，将该节点周围未添加过的一度节点加入队列；以此类推，直至遍历完所有节点。

使用邻接表储存图的信息。

在BFS的过程中，遍历到以上情况时，可将当前节点及其相邻节点删去，并记录当前的dist。

Python 代码：