サイクルを \(K\) 個用意し，それに沿って \((1,2)\) を動かすという設定です． 以下に示すように，定数通りの場合分けで解くことができます．

\(K=0\): 自明です．

\(K=1\): \((1,2)\) の行き先を並べ，これをグラフの有向辺と見ます．すると，長さ \(d\) (\(d\) は \(2\) 以上の \(N\) の約数) のサイクルが \(N/d\) 個並んだ形になるべきです． よって，入力の \((A_i,B_i)\) を全部含むサイクル分解が存在するか判定すればよいです．

\(K=2\): \(N\) の偶奇で更に場合分けします．

\(N\) が偶数: \(2\) つのサイクルを用意することで，すべての \((i,j)\) (\(i \neq j\)) を達成可能です． 具体的には，まずサイクル \((1,2,\ldots,N)\) を用意します． もう一つのサイクル \(a=(a_1,a_2,\ldots,a_N)\) は，以下の条件を満たせばよいです．

• 各 \(v\) について，\(a\) 内での \(v\) と \(v+1\) の距離（\(v\) から何回右に進んだら \(v+1\) になるか）を考える． すると，これらが \(1,2,\ldots,N-1\) の値を網羅する．

このような \(a\) は次のように構成できます． 値 \(1,2,\ldots,N\) を置く位置を決める際，\(1\) から始めて，\(1\) 右に進む，\(2\) 左に進む，\(3\) 右に進む，・・・と続けていけばよいです（正確なやり方は実装例を参照してください）．

\(N\) が奇数: まず，どんな \(2\) つのサイクルを用意しても，達成できない \((i,j)\) が存在することを示します． \(1\) 個目のサイクルにより \((1,2)\) から達成可能なペアを \((x_i,y_i)\) とします． 各 \((x_i,y_i)\) に対し，\(2\) 個目のサイクルにおける \(x_i\) と \(y_i\) の距離を \(z_i\) とします． ここで，\(z_i\) の総和は \(N\) の倍数となるはずです． しかし，\(z_i\) に \(1,2,\ldots,N-1\) がすべて含まれているとすると，残りの一つは \(0 \mod N\) になってしまいます． これは不可能なので，達成できないペアが存在することがわかります．

上記の証明から，\(2\) 番目のサイクルにおいて，少なくとも \(1\) つの距離が達成できないことがわかります． 逆に，\(1\) つの距離を決めると，これ以外の距離を全部達成するようなサイクルが構成できます． 具体的な構成は次のとおりです．

• 距離 \(1,2,\ldots,N-1\) を \(1\) 回ずつ使い，もとの場所に戻ってくるような移動方法を考える．この移動では \(N-1\) 箇所しか訪れないので，\(1\) 箇所余ることになる． そこで，利用しないと決めた距離 \(d\) の移動を消し，変わりに余った場所を経由するように組み替えることで，長さ \(N\) のサイクルが得られる．

「距離 \(1,2,\ldots,N-1\) を \(1\) 回ずつ使い，もとの場所に戻ってくるような移動方法」の構成は，説明が煩雑になるので実装例を参照してください（\(N \bmod 4\) で分類し，\(N\) が偶数のときの構成を張り合わせるような感じです）． あとは入力の \((A_i,B_i)\) に含まれない \((u,v)\) がサイクル分解になるかどうかを判定すれば，\(K=2\) のケースを解けます． サイクル分解に応じて，答えとなる \(1\) 番目のサイクルもきちんと計算する必要があることに注意してください．

\(K=3\): \(N\) が \(5\) 以上の奇数なら，すべての \((i,j)\) を達成できます． \(K=2\) の構成をほぼそのまま用います． \(2\) 番目のサイクルでは，距離 \(1\) を使わないようにしておきます． \(2\) 番目のサイクルが \(b_1,b_2,\ldots,b_N\) だった場合，\(3\) 番目のサイクルは \(b_2,b_1,b_3,b_4,\ldots,b_N\) とすればよいです． これが条件を満たすことは場合分けで確認できます．

上記に当てはまらないケース: このとき \(N=3\) です． \((1,2)\) の行き先から \(3\) の行き先もわかるわけですが，行き先 \((q_1,q_2,q_3)\) の転倒数の偶奇を考えると，常に不変であることがわかります． よって，この偶奇が異なる状態は絶対に達成できません． また逆に偶奇の制約が満たされている場合は \(K=1\) で構成できます．

以上を実装すればこの問題を解けます． 入力からサイクル分解を求める部分がボトルネックになり，例えば\(O(3^N)\) で解けます．

回答例(C++)