The following is an alternative implementation strategy by the tester for the part that finds the next vertex to proceed to.

For each vertex in \(G_2\), we maintain in a priority queue the “smallest number among vertices of the corresponding connected component in \(G_1\) that have not yet been added to the answer” for each adjacent vertex. The minimum number may change incrementally, but we update it at the time of retrieval from the priority queue. The specific procedure is as follows:

• Let \(v\) be the minimum number at the front of the priority queue, and \(g\) be the connected component containing \(v\) in \(G_1\).
• If we cannot proceed to a vertex in component \(g\), remove \(v\) from the front and return to the start of the procedure.
• If the answer does not yet contain \(v\), then \(v\) is the next vertex.
• Otherwise, remove \(v\) from the front, let \(u\) be a number not yet in the answer among the vertices in component \(g\), add \(u\) to the priority queue, and return to the start of the procedure.

This strategy does not explicitly use sqrt decomposition, but the total time complexity can be proved to be \(O((N+M)^{1.5} \log N)\). Note that multi-edges must be stored together.

Implementation (https://atcoder.jp/contests/arc216/submissions/74341810)