JM有一个魔法果园,里面一共有 n 棵苹果树,编号为 1,2,...,n 。这些苹果树之间通过 n−1 条魔法线相连,每一条魔法线可以连接两棵不同的苹果树,不存在两条魔法线连接的两对苹果树是完全相同的。
由于昨天cty在山上胡乱释放大型魔法,导致果园受到了扰乱,魔法线的连接结构全都变了,这可把JM弄懵逼了。因为以前他是知道这些魔法线恰好能将这些苹果树全部连通的,意思是,对于任意两棵苹果树,它们总能经过若干条魔法线直接或间接地连接上。而现在它们是不是全部连通的就是个未知数了。
JM还要忙着去把cty抓去喂qz,所以他没空,希望你能帮他判断一下,现在这些苹果树是否还是全部连通的。如果不连通,那么JM就要花费大量的精力去修正了,如果连通的话,你还需要帮他重新构建游客指引。
因为魔法果园是一个9A级景点,游客参观量是非常大的。果园的 1 号苹果树最为健壮,它种在大门口,游客们首先会被引导到这里。接下来,游客们总是随着魔法线的指引进行后续的参观。因为果园只有一个出入口且游客们的体力有限,所以他们总是会希望知道,自己当前距离 1 号苹果树的最短距离是多少。