次に進むべき頂点を見つける部分について，tester による別の実装方針です．

\(G_2\) の各頂点において，各隣接する頂点の「対応する \(G_1\) の連結成分の頂点のうち，まだ答えに追加されていない最小の番号」を優先度付きキューで保持することにします．最小の番号は逐次変化する可能性がありますが，優先度付きキューで取り出す際に更新も同時に行うことにします．具体的な手順は以下の通りです．

• 優先度付きキューの先頭にある最小の番号を \(v\)，\(G_1\) において \(v\) が属する連結成分を \(g\) とする．
• \(g\) に属する頂点に進めないのであれば，先頭から \(v\) を削除し，手順の先頭に戻る．
• 答えにまだ \(v\) が含まれていないならば，次の頂点は \(v\) である．
• そうでない場合，先頭から \(v\) を削除し，\(g\) の連結成分の頂点のうちまだ答えに追加されていない番号を \(u\) として，\(u\) を優先度付きキューに追加し，手順の先頭に戻る．

この方針は陽に平方分割していませんが，計算量は全体で \(O((N+M)^{1.5}\log N)\) になることが証明できます．多重辺をまとめて持つ必要があることに注意してください．

実装例（https://atcoder.jp/contests/arc216/submissions/74341810 ）