题目描述

C 国共有 $n$ 个城市。有 $n-1$ 条双向道路，每条道路连接两个城市，任意两个城市之间能互相到达。为了使得交通更加便捷，C 国智囊团打算新建一条连接两个城市的道路，使得某些城市之间的最短距离能够比原来更小。现在智囊团共提出了 $m$ 个备选方案，你需要回答每个方案能够使得多少对城市的最短距离减小。

C 国的 $1$ 号城市特别重要，因此，$1$ 号城市到任意一个城市的简单路径上至多包括 $100$ 个城市。

输入格式