必要条件 \(Y[Y[i]]=i\) は仮定しておきます．

[1] 辺彩色による言い換え

本問題は，無向グラフの辺彩色に関する問題に言い換えられます．具体的には以下の通りです．

【言い換え問題文】

\(G=K_N\) を \(N\) 頂点（無向）完全グラフとする．\(G\) の各辺に色 \(1, 2, \ldots, N\) を割り当てて，以下の条件が成り立つようにしてください．

• この割り当ては辺彩色である．つまり，各頂点に接続する辺に塗られた色は相異なる．
• 色 \(1\) で塗る辺集合は入力で与えられる．

対応は \(A_{i,j}\) を，頂点 \(i,j\) 間の辺の色と見なすものです．言い換えにおいて対角成分の扱いがやや非自明ですが，以下のように確認できます．

• 問題の条件を満たす \(A\) から，言い換え問題文の辺彩色が得られる：単に対角成分を無視すればよい．
• 言い換え問題文の辺彩色から，問題の条件を満たす \(A\) が得られる：対角成分にはその頂点で使われていない唯一の色を割り当てればよい．

辺彩色において，ひとつの色はマッチングをなすので，完全グラフの辺集合をマッチングに分解すると考えておくのも理解の役に立つと思います．

[2] \(N\) が奇数の場合

\(K_N\) の最大マッチングの大きさは \(\lfloor N/2\rfloor=(N-1)/2\) です．よって，完全グラフを \(N\) 個のマッチングに分割するには，ひとつひとつのマッチングが最大マッチングでなければいけません．特に，色 \(1\) の辺の個数がちょうど \((N-1)/2\) であるというのが必要条件になります．

この必要条件のもと，目標の辺彩色を構成可能です．頂点の名前を適当に付け直すことで，グラフの頂点は \(0,1,\ldots,N-1\) の \(N\) 個で，入力では \(x+y\equiv 0\pmod{N}\) のを満たす辺 \(\{x,y\}\) 全体が色 \(1\) のマッチングとして与えられているとしてよいです．

このとき，色 \(c=2,3,\ldots,N\) に対して，\(x+y\equiv c-1\pmod{N}\) となる辺 \(\{x,y\}\) を色 \(c\) の辺とすれば条件を満たす辺彩色が得られます．

[3] \(N\) が偶数の場合

\(K_N\) は \((N-1)\) 色で辺彩色可能です．これは，[2] の方法で \(K_{N-1}\) を \((N-1)\) 色で辺彩色したあと，それに新しく \(1\) 頂点を追加する（辺は \(N-1\) 個追加する）ことを考えれば分かります．追加する辺には，既存の \(N-1\) 点の側で未使用の唯一の色を割り当てるようにします．

本問を解くには，まずこの方法で \(K_N\) の辺を色 \(2,3,\ldots,N\) で彩色しておきます．そのあと，入力で色 \(1\) であると指定されている辺を色 \(1\) で上書きすればよいです．

[4] 参考

次の結果は有名です．上の解説の議論で非自明な部分はほとんど証明できているので，確認してください．

• \(N\) が奇数ならば，\(K_N\) の辺彩色数は \(N\) である．
• \(N\) が偶数ならば，\(K_N\) の辺彩色数は \(N-1\) である．