まず，\(S=\)0\( \times N\) (0 が \(N\) 個並んだ文字列)，\(T=\)1\( \times N\) で初期化します．

ここから以下の \(2\) 種類の操作を繰り返して条件を満たすことを目指します．

• \(S\) の末尾に 0，\(T\) の末尾に 0 を追加する．
• \(S\) の末尾に 1，\(T\) の末尾に 0 を追加する．

操作の過程において，まだマッチしていない 0, 1 がどの連結成分に属すかを保持します． \(S\) 側にある未マッチの 0 が属す連結成分を (0 の登場する順に) \(x_1,x_2,\cdots,x_k\)，\(T\) 側にある未マッチの 1 が属す連結成分を \(y_1,y_2,\cdots,y_k\) とおくことにします．

\(S,T\) に 0,0 を追加する操作を考えると，\(x\) を \(1\) つ左へサイクリックシフトする操作に対応します．

\(S,T\) に 1,0 を追加する操作を考えると，\(x_1,y_1\) を \(x,y\) から取り除き，\(x_1,y_1\) の間に辺を張る操作に対応します．

これらの操作を組み合わせて \(A\) の条件を満たすことを考えます． まず適当な順列 \(P\) を用意して，\(P\) のサイクル分解が \(A\) と整合するようにしておきます． あとは，\(x_1=A_{y_1}\) のタイミングで \(x_1,y_1\) を結ぶように操作すれば良いです．

操作回数は \(O(N^2)\) です．

解答例(C++)