P5512 [NOIP 1997 提高组] 棋盘问题 加强版

题目背景

P1549 数据加强版。

数据从 5 扩大到了 10。

因为本题数据可能存在诸多争议，故特开一题用来测试加强版数据。

题目描述

在 \(N \times N\)（\(1 \le N \le 10\)）的棋盘上，填入 \(1, 2, \dots, N ^ 2\) 共 \(N ^ 2\) 个数，使得任意两个相邻的数之和为素数。

例如：当 \(N = 2\) 时，有：

其相邻数的和为素数的有：

\(1+2,1+4,4+3,2+3\)

当 \(N=4\) 时，一种可以填写的方案如下：

在这里我们约定：左上角的格子里必须填数字 \(1\)。

输入格式

一行一个整数 \(N\)。

输出格式

如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出 NO。

输入输出样例 #1

输入 #1

2

输出 #1

1 2
4 3

输入输出样例 #2

输入 #2

1

输出 #2

NO

说明/提示

\(N\leq10\)

\(N=1,2,...,10\) 的数据都各有一个点，由于某些原因， \(N\) 不一定与测试点编号相等。

数据新修复于 2020.1.20