本题可使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来求解村庄间的最短路径，以下是使用BFS算法的C++代码实现：
代码解释：
1.首先定义了图的存储结构 graph 为邻接表，dist 数组用于记录从起点到各点的距离。
2.bfs 函数实现了广度优先搜索算法，从起点 start 开始搜索，直到找到终点 end，并记录路径距离。
3.在 main 函数中，先读取测试数据组数 T，对于每组测试数据，读取村庄数量 n 和询问数量 m ，然后读取 n - 1 条边的信息构建图。接着对于每个询问，调用 bfs 函数求解并输出结果。最后在每组测试数据结束后，清空图的邻接表并输出一个空行。
最终代码：
