\(M ≤ N + 10\) とグラフが木に非常に近いことに注目します。

まずは、グラフが木の場合の解法を考えてみましょう。
適当に根を取り、全ての頂点について根からの最短距離を計算します。 根から頂点 \(i\) への最短距離を \(\mathrm{dist}(i)\) と表します。
頂点 \(x\) から頂点 \(y\) への最短距離は、頂点 \(x\) と頂点 \(y\) の最小共通祖先 を \(\mathrm{lca}(x, y)\) として、\(\mathrm{dist}(x) + \mathrm{dist}(y) - 2 \times \mathrm{dist}(\mathrm{lca}(x, y))\) です。
最小共通祖先は、ダブリング を使う方法や RMQ を使う方法でクエリ \(O(\log N)\) で求めることができます。

グラフが木ではない場合は、グラフの全域木を \(1\) つ取り、全域木とそれ以外の辺に分解します。全域木を通る場合の最短距離は高速に計算できるので、全域木以外の辺の両端と頂点 \(u_i, v_i\) のみに注目する Dijkstra 法で解くことができます。

時間計算量は、\(d = M - N + 1\) として、\(O(N\log N + Q(d^2+d\log N))\) です。

回答例 (C++)

回答例 (Python)