まず、同じ州同士を結んでいる辺は縮約してよいです。 これにより、同じ州同士に対するクエリは \(O(1)\) で答えられます。

これにより辺は異なる州を結び、クエリは異なる州に属する街の間のものに限られるとしてよいです。

クエリを先読みし、同じ州の組に関するクエリをまとめて処理します。州の組 \((a, b)\) について回答するとき、union-find を用いて州の組 \((a, b)\) を結ぶ辺を全て unite してから回答します。

毎回、\(O(N)\) で union-find を初期化すると計算量が間に合いませんが、

• undo ができる unionfind を用いると \(O(Q + (N+M)log(N + M))\)
• そのとき見た頂点のみの親を初期化すれば \(O(Q + (N + M)log(N + M))\)
• 同じ州の組をまとめるところに hashmap を用いると \(O(Q + (N + M)\alpha(N))\)

で解くことができます。