雪莉实验机
Migrated from Lutece 2723 雪莉实验机
All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.
Description
雪莉实验机背后的故事要从很久——很久——很久——以前说起......
（又是为二次元人物真情实感的一天）
恩佐其实是一个很悲剧的人物。
尤其是和洛克对比的时候。
洛克和恩佐，同样是天赋极高的天才，同样是被格里芬院长看重的优生，同样是年少有为的大魔法师。
一个正直善良，挚友成群，勇敢坚毅地追逐正义，长成了所有人和自己都希望的样子。
而另一个则步入“歧途”，孤独一生。身边虽有几个还算忠心的下属，可他想要的却从未得到过，一生都活在自己可怜的执念里。
我在一些恩雪的视频下面，看到有人说“洛克他们都是温室里的花朵”，其实这么说并不对。
洛克和可丽希亚经历了这么多风风雨雨，早就成长为独当一面的大魔法师了。
洛克和恩佐不同的地方是，他性格好，人缘好，同学师长都对他特别好，整个王国都是他的真心朋友，我猜他家庭应该也很幸福，一看就是在爱里长大的孩子。他接受了来自这个世界那么多的温暖和善意，他没有理由不去爱、不去回报这个世界。而且他骨子里也有一股坚毅、正直，这么十全十美的人没人不喜欢。
但其实这么完美也挺招人恨的。因为现实中的我们没有这样的主角光环，我们大多要经历更多的磨难，体会更多的人心险恶。
所以比起正直善良的洛克，恩佐反而让我更心疼。
恩佐是个坏人，他烧杀抢掠，多少次搞的全国鸡犬不宁。他固然可恨，可这一切的罪过难道都只是他一个人的错吗？当然不。
幼时丧亲，格里芬院长虽然收养了他，却也只是给了他一个家的住所，却没人能给他家的温暖。
儿时丧友。天赋极高，注定了他的优秀，却也注定了他的孤独。被抛弃和缺爱的敏感又养成了他孤僻的性格，难以交到知心朋友。好不容易得一挚友，却也只是短暂的温暖，不久又承受失去挚友的痛苦。
直到雪莉老师的出现，给他的世界带来了最后的，也是最致命的温暖。18岁的老师，自己还稚气未脱，却要装成大人的模样，对付这个16岁的学生。她温柔，可爱，又是唯一真心对恩佐好的人，怎么能不走进他尘封的心？他们朝夕相处，共同进步。老师也好，朋友也好，恋人也好，无论哪个词，形容她在恩佐心中的地位都太肤浅。她早就成了恩佐的信仰啊。
如果恩佐是像洛克那样，从小被爱环绕的人，或许雪莉老师的离开，还不会给他造成那么大的伤害。
可是，快渴死的鱼，对水的渴望，是拼尽了全身气力的。
我只有一颗糖，你凭什么要求我大方？
“你走了以后，所有人都说我疯了。”
“就算世界与我为敌，我也一定会完成大业
到那时，我们应该就可以再见面了吧”
“难道我不也是，日月经年，岁岁难过，却岁岁过”
我拼尽全力，为的只不过是再见你一面。
可我好不容易复活的你，为了这个世界，再一次选择了抛弃我。
你把他们都复活了，那我呢？
站在恩佐的角度，或许他也没什么错。为什么要用他最亲最温暖的雪莉老师，去换那个所有人都对他冷冰冰的世界呢？
这不公平
我没有背弃世界。
因为你就是我的全世界。
恩佐想要建造雪莉实验机，他需要很多零件，这些零件分布在一棵树上，他每次取两个零件组装在一起就需要知道这两种零件的距离。由于恩佐修炼黑魔法走火入魔已神志不清，maco想要帮他实现愿望。可惜maco身边全是卷王，终日焦虑，分身乏术，这个问题只能交给你来解决了
Input
第一行两个正整数 和 ，分别表示共 种零件，有 次组装。 接下来 行，每行两个整数 和 ，表示第 种零件 和 第 种零件的距离为 ，而其它零件之间的距离均为无穷大。 接下来 行，每行两个整数 和 ，表示查询第 种零件和第 种零件的最短距离。 输入数据保证合法。
Output
输出共 行，每行有且只有一个正整数，是对于第 次询问的回答，即两种零件的最短距离。
Samples
6 3
1 2
1 5
5 3
5 6
3 4
1 6
2 4
3 5
2
4
1
10 7
1 2
2 3
2 4
3 5
3 6
4 7
4 8
4 9
9 10
1 10
2 9
3 8
4 7
1 7
2 6
3 5
4
2
3
1
3
2
1
Note
如果你也喜欢恩雪cp，maco鼓励你在解题报告里面表达你的喜欢，虽然没有加分
Resources
2023 UESTC ICPC Training for Graph