\(dis[i][j](1 \leq i \leq K, 1 \leq j \leq N)\) を、街 \(a_i\) から街 \(j\) までの最短距離とします。これらの値は BFS などを用いると \(O(KM)\) で前計算することができます。

すると、クエリ \((s,t)\) に対する答えは、\(\underset{1 \leq i \leq K}{min}(dis[i][s]+dis[i][t])\) です。

計算量は \(O(KM+QK)\) です。

実装例：https://atcoder.jp/contests/past202112-open/submissions/28264738