不是很困难的一道题，但因为最后一步遗憾止步 分。

首先考虑树且 的情况。先把所有边变成 问一遍，那么 到 最短路就是 ，考虑用这个解出 的层数，然后在对应层进行二分，每次找到一个前缀 ，把这个前缀中的点及其祖先边都变成 ，其余边都变成 。如果此时问出来仍然等于原来的结果，那就说明 在这个前缀里。进一步地发现没有必要在对应层进行二分，直接在 BFS 序上二分即可。

上述做法可以拓展到图且 的情况，只要跑出以 为根的 BFS 树，然后将非树边设为 ，执行上述过程即可。（这里说明了为什么不能在二分时把要 check 的前缀设为 ，其余设为 ，这样在树上没有问题，但在图上就可能会有不同于树上 到 路径的最短路出现。将要 check 的前缀设为 ，其余设为 ，如果 在 check 范围内，结果一定为 ，就能正确 check）。

接下来考虑两个点都不固定的情况。我们考虑找到一条中间边 使得存在 的路径（我一开始只是感觉要找中间点，没有想清楚，于是没有想出最后一步）。我们考虑直接在边序列上二分，check 时先把所有边设为 ，然后将一个前缀变为 ，如果此时答案不等于初始值，说明这个前缀里肯定有一条在 路径上的边。找出来 后，以 为根和以 为根都跑一遍 BFS，将与 距离严格小于与 距离的点放入点集 ，严格大于的放入点集 。那么有 。在 内部就是两个图且有一个点为 的子问题，两次二分 即可。

总操作次数上界为 ，实际数据卡不满 次。