AT_codequeen2023_final_b N-Queens Problem

有一个由 $N$ 行 $N$ 列组成的网格棋盘。我们将从上往下第 $i$ 行（$1 \leq i \leq N$）、从左往右第 $j$ 列（$1 \leq j \leq N$）的格子称为格子 $(i, j)$。 在棋盘上已经放置了 $N-1$ 个皇后，第 $i$ 个皇后位于格子 $(r_i, c_i)$。 若棋盘满足以下条件，则称该棋盘为**良好状态**： - 在任何一条垂直、水平或 $45$ 度斜线（即所有行、列、两种对角线）上，至多只能有 $1$ 个皇后。 保证给定的棋盘一定是*良好状态*。 请判断是否可以在该棋盘上再放置 $1$ 个皇后，且放置后棋盘仍然是*良好状态*。如果可以，请输出一个可以放置的位置。如果无法放置，请输出 `-1`。

输入通过标准输入给出，格式如下： > $N$ $r_1$ $c_1$ $r_2$ $c_2$ $\cdots$ $r_{N-1}$ $c_{N-1}$

如果存在某个格子 $(i, j)$ 可以放置皇后，输出： > $i$ $j$ 若无法放置，输出 `-1`。 如果有多个解，输出任意一个均可。

### 样例解释 1 对于格子 $(2, 4)$，经过其所在的所有行、列和 $45$ 度斜线，都没有皇后。因此，在 $(2, 4)$ 放置皇后后，依然可以保持*良好状态*。  ### 数据范围 - 输入均为整数。 - $2 \leq N \leq 5,\!000$ - $1 \leq r_i, c_i \leq N$，$(1 \leq i \leq N - 1)$ - 给定的棋盘保证是*良好状态*。 由 ChatGPT 5 翻译