$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