データ構造を利用した別解を簡単に紹介します。
想定解にある言い換え + いくらかの考察により、\(2N\) 頂点の無向グラフに対して次の 2 種類のクエリを高速に処理するデータ構造が存在すればこの問題を解くことが出来ます。

• merge(a, b, l) : \(i=0,1,2,\dots,l\) について, 頂点 \(a+i\) と頂点 \(b+i\) の間に辺を張る。
• leader(a) : 頂点 \(a\) が所属する連結成分の代表元を返す。

このようなクエリは、 Range Parallel Unionfind (仮称) と呼ばれるデータ構造を利用することで、クエリ処理の部分を全体で \(\mathrm{O}(N \alpha(N))\) や \(\mathrm{O}(N \log N \alpha(N))\) や \(\mathrm{O}(N \log^2 N)\) で処理することが出来て、これは十分高速です。

• \(\mathrm{O}(N \log^2 N)\) のデータ構造 : https://github.com/yosupo06/library-checker-problems/issues/934 の SSRS さんの投稿
• \(\mathrm{O}(N \log N \alpha(N))\) のデータ構造 : https://img.atcoder.jp/yahoo-procon2018-final-open/editorial.pdf の D 問題の解法
• \(\mathrm{O}(N \alpha(N))\) 解法に関する情報 : https://yosupo.hatenablog.com/entry/2019/11/12/001535

(注 : 2 番目と 3 番目のアルゴリズムは merge クエリを処理し終えた後に same クエリが来る場合にのみ使用可能です)