为了随时与 rainbow 快速交流，Freda 制造了两部传呼机。Freda 和 rainbow 所在的地方有 座房屋、 条双向光缆。每条光缆连接两座房屋，传呼机发出的信号只能沿着光缆传递，并且传呼机的信号从光缆的其中一端传递到另一端需要花费 单位时间。现在 Freda 要进行 次试验，每次选取两座房屋，并想知道传呼机的信号在这两座房屋之间传递至少需要多长时间。Freda 和 rainbow 简直弱爆了有木有 T_T，请你帮帮他们吧……
座房屋通过光缆一定是连通的，并且这 条光缆有以下三类连接情况：
- 光缆不形成环，也就是光缆仅有 条。
- 光缆只形成一个环，也就是光缆仅有 条。
- 每条光缆仅在一个环中。
