想定解とは別の構築方法を示します．

まず，長さが最大のウォーク（偶数の場合 \(N^2\)，奇数の場合 \(N^2-N+1\) ）を一つ求めます．このとき，ウォークの先頭 \(N\) 辺について，\(i\) 番目の辺が結ぶ左の頂点を \(u_i\) 、右の頂点を \(v_i\) としたとき，\(v_i-u_i\) が相異なるようなウォークを取ります．（☆）

これは，例えば \(l_1,r_N,l_2,r_{N-1},\ldots\) という形で最初の \(N\) 辺を取り，残った辺のオイラー路を求めることで構築できます．（\(N\) が奇数の場合は例えば辺 \((l_2,r_1),(l_3,r_2),\ldots,(l_N,r_{N-1})\) を削除したグラフ上でオイラー路を求めることで上界を達成できます．）

各辺に \(1\) から \(K\) の色を割り当てることとします．また，長さ \(N\) の配列 \(a=(-1,\ldots,-1)\) を用意します．

求めたウォークの先頭 \(K\) 辺には，先頭 \(i\) 番目に色 \(i\) を割り当てます．このとき，\(i\) 番目の辺が頂点 \(l\) と頂点 \(r\) を結ぶとき，\(c:=(r-l)\bmod N\) と定義し，\(a_c=-1\) ならば \(a_c=i\) とします．

（☆）より，この手続きの終了時 \(a\) は \((1,\ldots,N)\) の順列となっています．

色が未確定のそれぞれの辺 \((l,r)\) には色 \(a_{(r-l)\bmod N}\) を割り当てます．

最後に，色が小さい順に小さな数を書き込みます．

この数字の書き込み方は実は条件を満たしています．同じ色の辺同士は色の割り当て方法より隣接していないことから，数が増加するとき必ず色の値も増加します．よって \(K+1\) 以上の長さの狭義単調増加なウォークが存在しないことが言えます．