CF1919G Tree LGM

现在有一个游戏 : 在一棵**有根树**上的某一节点处有一个标记. 两名玩家轮流将这个标记移至当前标记所在节点的任意一个子节点处, 先到达叶子节点处 (即让对方无路可走) 者胜利. 双方均采取最佳策略. 给定 $n$ 和一个大小为 $n\times n$ 的二维数组 $S$ 满足 $S_{i, j}\in\{0, 1\}$. 其代表一棵大小为 $n$ 的树, 若 $S_{i, j} = 1$ 则当选择 $i$ 为根, 标记在 $j$ 处时先手必胜, 否则此时后手必胜. 请构造一棵符合要求的树, 或者输出无解.

输入一个整数 $n$, 然后输入 $n$ 行, 每行 $n$ 个整数, 第 $i$ 行第 $j$ 列代表 $S_{i, j}$, **注意两个数间没有空格分隔**. 保证 $1\le n\le 5000$.

如果存在符合要求的树, 输出 `YES`, 然后输出 $n - 1$ 行, 每行输出两个整数 $x, y$, 代表树的一条边. 如果有多种满足条件的情况, 输出任意一种即可. 否则只输出一行 `NO`. 注意输出对大小写不敏感. Translated by @[Ja50nY0un9_as_AgNO3](/user/363302).

In the first test case, the line graph $ 1\!-\!4\!-\!2\!-\!3 $ satisfies the winning and losing states represented by matrix $ s $ . For example, $ s_{3,3} = 1 $ as the first player can move the coin from $ 3\rightarrow 2 $ , then the second player moves the coin from $ 2\rightarrow 4 $ , and finally, the first player moves the coin from $ 4\rightarrow 1 $ . At this point, $ 1 $ has no children, so the second player is unable to make a move and loses. On the other hand, $ s_{1,3} = 0 $ as if $ 1 $ is the root, then $ 3 $ has no children so the first player is unable to make the first move and loses. In the second test case, it is possible to prove that no tree satisfies the winning and losing states represented by matrix $ s $ .