문제

2025 충남대학교 SW-IT Contest에 출제되었던 Grid Traveler 문제는 정수 $N$이 주어질 때 승현이의 여행이 가능한 $N \times N$ 격자가 존재하는지 판별하고, 존재한다면 그런 격자를 하나 출력하는 문제였다.

승현이의 여행은 다음과 같이 진행된다.

• $1$이 적힌 칸에서 시작한다.
• 각 정수 $i$ $(1 \le i < N^2)$에 대해, 현재 $i$가 적힌 칸에서 정확히 $i$번 이동하여 $i+1$이 적힌 칸에 도달해야 한다. 이 과정을 방문이라고 하자.
• 한 번의 이동은 격자의 경계를 벗어나지 않으며 상하좌우로 인접한 칸으로 이동하는 것이다.
• 하나의 방문 과정 안에서는 같은 칸으로 두 번 이상 이동할 수 없다. 서로 다른 방문 과정에서 같은 칸을 다시 사용하는 것은 허용된다.

예를 들어 $N=2$일 때, 아래 격자는 승현이의 여행이 가능한 격자이다.

1 2
3 4

$1$에서 정확히 $1$번 이동하여 $2$에 도달할 수 있고, $2$에서 정확히 $2$번 이동하여 $3$에 도달할 수 있으며, $3$에서 정확히 $3$번 이동하여 $4$에 도달할 수 있다.

반면 아래 격자는 승현이의 여행이 가능한 격자가 아니다.

1 2
4 3

$2$에서 정확히 $2$번 이동하여 $3$에 도달할 수 없기 때문이다.

$1$부터 $N^2$까지의 정수가 한 번씩 적힌 $N \times N$ 격자가 주어진다. 이 격자가 승현이의 여행이 가능한 격자인지 판별하는 프로그램을 작성하시오.

입력

첫째 줄에 격자의 크기 $N$이 주어진다. $(2 \le N \le 1,000)$

둘째 줄부터 $N$개의 줄에 걸쳐 격자가 주어진다. 각 줄에는 $N$개의 정수가 공백으로 구분되어 주어진다.

격자에 적힌 수는 $1$ 이상 $N^2$ 이하이며, 각 수는 정확히 한 번씩 등장한다.

출력

주어진 격자가 승현이의 여행이 가능한 격자라면 YES, 아니면 NO를 출력하시오.

예제 입력 1

2
1 2
3 4

예제 출력 1

YES

예제 입력 2

2
1 2
4 3

예제 출력 2

NO