\(N\) が奇数のときは、隣接行列で斜めの「線」を隣接させることで解を作れます。\(N = 5\) の場合の例を記します。

5 5 3 3 1 1
4 5 5 3 3 4
4 4 5 5 3 3
2 4 4 5 5 2
2 2 4 4 5 5

グラフの用語を使うと次の通りです。

1. \(1 \leq i, j \leq N\) については、辺 \(v_i u_j\) の色を \({\lfloor (j - i) / 2 \rfloor}\) のみに基づいて決め、
2. \(v_i\) を終点とする唯一のパスを辺 \(v_i u_{N + 1}\) で伸ばす。

\(N\) が偶数のときは、この構成はそのままでは使えません。「1.」の後で、各 \(v_i\) を終点とするパスが \(0\) 本か \(2\) 本あるからです。しかし、\(1 \leq i, j \leq N - 1\) については「1.」の構成を再利用し、多少の調整を加えつつ \(v_N, u_N, u_{N + 1}\) にパスを伸ばすことができます。詳細は以下の通りです。

\(N = 2\) の場合は、解はありません。\(N\) が他の偶数の場合は、次のようにして解を作ることができます。

• \(1 \leq i, j \leq N - 1\) について、\(\lfloor (j - i) / 2 \rfloor\) の値に基づいて辺 \(v_i u_j\) を色 \(2, \ldots, N\) のいずれかで塗る。\(N = 6\) の場合の例を記す。

6 6 4 4 2 . .
5 6 6 4 4 . .
5 5 6 6 4 . .
3 5 5 6 6 . .
3 3 5 5 6 . .
. . . . . . .

• 各色 \(2, \ldots, N\) のパスを最下行に伸ばし（この方法は一通りしかない）、右端の空き列のいずれかにも伸ばす。このとき、各パスについて、ある \(1 \leq i \leq N / 2, j \in \{N, N + 1\}\) に対して辺 \(v_{2i - 1} u_j, v_{2i} u_j\) が含まれるようにする。また、残りの \(2\) 本の辺で色 \(1\) のパスを作る。このとき、このパスが色 \(2\) のパスと同じ列にあるようにする。

6 6 4 4 2 5 2
5 6 6 4 4 5 2
5 5 6 6 4 4 3
3 5 5 6 6 4 3
3 3 5 5 6 6 1
6 3 4 5 2 6 1

• 唯一の問題は、色 \(N\) のパスがサイクルになってしまったことである。色 \(1, 2, N\) のパスを組み替えてこれを解決する。

6 6 4 4 2 5 2
5 6 6 4 4 5 1
5 5 6 6 4 4 3
3 5 5 6 6 4 3
3 3 5 5 6 6 1
2 3 4 5 2 6 6