#P18118. Jump Cycle

Jump Cycle

Jump Cycle

给定偶数 nn,考虑行、列编号均为 1,…,n1,\ldots,n 的正方形网格。把全部 n2n^2 个格子排列为一个循环序列 p1,…,pn2p_1,\ldots,p_{n^2},每个格子恰好出现一次,并规定 pn2+1=p1p_{n^2+1}=p_1。

若 pi=(ri,ci)p_i=(r_i,c_i),要求相邻两格同行或同列,且

∣ri−ri+1∣+∣ci−ci+1∣=((i−1) mod 4)+1.|r_i-r_{i+1}|+|c_i-c_{i+1}|=((i-1)\bmod4)+1.

也就是说,依次跳跃1、2、3、4格并循环,包括最后返回起点的跳跃。构造任意满足要求的循环;若无解则报告。

输入格式

一行一个偶数 nn,4≤n≤2004\le n\le200。

输出格式

无解时输出一行 NO。

有解时先输出 YES,再输出一个 n×nn\times n 整数矩阵。第 rr 行第 cc 列的值为 kk,表示 pk=(r,c)p_k=(r,c)。矩阵必须包含 1,…,n21,\ldots,n^2 各一次。存在多个答案时输出任意一个。

样例

8
YES
1 7 25 26 8 27 37 38
2 60 23 33 59 48 42 41
5 6 16 34 57 46 45 39
3 21 22 52 58 28 43 53
64 19 24 35 9 47 36 54
62 61 15 32 10 49 31 40
4 18 17 51 56 50 44 55
63 20 14 13 11 29 30 12