Description

给定一个由 0 和 1 组成的 $n \times n$ 二进制矩阵。初始时，你有一个空字符串 $S$。你从位置 $(0,0)$（左上角）出发，每次只能向右或向下移动。将经过的每个元素按顺序添加到字符串 $S$ 中。

判断是否存在一条路径使得 $S$ 成为回文串。如果存在，输出这样的路径；否则输出不存在。

注意每个矩阵都是随机生成的。

Input Format

第一行包含一个整数 $n$ $(1 \le n \le 5\,000)$ —— 矩阵的大小。

接下来的 $n$ 行，每行包含 $n$ 个字符 $a_{i,j}$ $(0 \le a_{i,j} \le 1)$ —— 描述矩阵的内容。

输入矩阵是从所有可能的 $n \times n$ 有效矩阵中随机选取的。

Output Format

如果不存在这样的回文路径，输出一行 $\tt{NO}$。

否则，第一行输出 $\tt{YES}$。接下来的 $2n-1$ 行，每行输出两个整数 $x_i$ 和 $y_i$ ($0 \leq x_i, y_i < n$) —— 表示路径上第 $i$ 个单元格的坐标。

2
01
00

YES
0 0
0 1
1 1

4
0100
1010
0100
0001

NO

4
0010
1001
1010
0010

YES
0 0
0 1
0 2
0 3
1 3
2 3
3 3

Hint

• （$5$ 分）：$n \le 10$；
• （$9$ 分）：$n \le 100$；
• （$19$ 分）：$n \le 500$；
• （$27$ 分）：$n \le 1\,500$；
• （$40$ 分）：无额外限制。

翻译由 DeepSeek V3 完成