34535번 - Grid Traveler 스페셜 저지

문제

승현이는 $N\times N$ 격자에 살고 있다. $N^2$개의 각 칸에는 1ドル$부터 $N^2$까지의 정수 중 하나가 적혀있고, 각 칸에 적힌 수는 모두 다르다.

승현이는 아래 규칙을 지키면서 격자 안에서 여행하려고 한다.

• 1ドル$이 적힌 칸에서 시작한다.
• $i(1≤i<N^2)$가 적힌 칸에서 정확히 $i$번 이동하여 $i+1$이 적힌 칸에 도달한다. 이 과정을 방문이라 하자.
• 한 번의 이동은 격자의 경계를 벗어나지 않으며 상하좌우로 한 칸 이동하는 것을 의미하며, 각 방문 과정에서 같은 칸으로 두 번 이상 이동할 수 없다.

최종적으로 $N^2$이 적힌 칸에 도달할 수 있다면 승현이의 여행이 가능하다고 본다. 격자의 크기와 각 칸에 적힌 수에 따라 승현이의 여행이 가능할 수도, 불가능할 수도 있다. 격자의 크기가 주어질 때, 조건을 만족하면서 승현이의 여행이 가능한 격자를 만들어 주자.

입력

첫째 줄에 $N$이 주어진다. $(2≤N≤1,円 000)$

출력

승현이의 여행이 가능한 $N\times N$ 격자가 없다면, 첫째 줄에 NO를 출력한다.

가능한 격자가 있다면, 첫째 줄에 YES를 출력하고 둘째 줄부터 $N$개의 줄에 걸쳐 각 줄에 격자의 행에 해당하는 $N$개의 정수를 공백으로 구분하여 출력한다. 다시 말해, $i+1$번째 줄의 $j$번째 정수는 격자의 $i$번째 행의 $j$번째 열에 위치한 칸에 적힌 수를 의미한다.

정답이 여러 개라면 그중 하나만 출력한다.

제한

힌트