公式解説と同様グラフとして考えます．

\(4\) 辺 \((1,1)-(1,2),(1,2)-(1,3),(2,1)-(2,2),(2,2)-(2,3)\) を通る回数を決めると，他の部分を通る回数も一意に定まります．

従って上の \(4\) 箇所を通る回数の組を全探索し，対応するグラフが連結であればそれに対してオイラー路を構築すればよいです．

他の辺を通る回数が負にならないように探索範囲を制限することで，連結性を毎回 Union-Find で確認しても間に合うようになります．