CF1919G.Tree LGM

In TreeWorld, there is a popular two-player game played on a tree with $n$ vertices labelled from $1$ to $n$. In this game, the tournament leaders first choose a vertex to be the root of the tree and choose another vertex (possibly the same vertex as the root) to place a coin on. Then, each player will take turns moving the coin to any child$^\dagger$ of the vertex that the coin is currently on. The first player who is unable to make a move loses.

Alice wants to be a tree LGM, so she spends a lot of time studying the game. She wrote down an $n$ by $n$ matrix $s$, where $s_{i,j} = \mathtt{1}$ if the first player can win with the root of the tree chosen to be vertex $i$, and the coin was initially placed on vertex $j$. Otherwise, $s_{i, j} = \mathtt{0}$. Alice is a perfectionist, so she assumes that both players play perfectly in the game.

However, she accidentally knocked her head on the way to the tournament and forgot what the tree looked like. Determine whether there exists a tree that satisfies the winning and losing states represented by matrix $s$, and if it exists, construct a valid tree.

$^\dagger$ A vertex $c$ is a child of vertex $u$ if there is an edge between $c$ and $u$, and $c$ does not lie on the unique simple path from the root to vertex $u$.

在 TreeWorld 中，有一种流行的双人游戏，在一棵含有 $n$ 个顶点（编号为 $1$ 到 $n$）的树上进行。游戏中，比赛组织者首先选定一个顶点作为树的根，并在另一个顶点（可以与根相同）上放置一枚硬币。随后，双方玩家轮流将硬币沿树边移动到当前硬币所在顶点的任意一个子节点$^\dagger$。第一个无法进行移动的玩家判负。

Alice 希望成为树类 LGM（Legendary Grandmaster），因此她花费大量时间研究该游戏。她记录下了一个 $n \times n$ 的矩阵 $s$，其中当以顶点 $i$ 为根、硬币初始置于顶点 $j$ 时，若先手玩家有必胜策略，则 $s_{i,j} = \mathtt{1}$；否则 $s_{i,j} = \mathtt{0}$。Alice 是一名完美主义者，因此她假设双方均采用最优策略进行游戏。

然而，她在前往比赛途中不慎撞到了头，忘记了这棵树的具体结构。请判断是否存在一棵树，使得其对应的胜负状态恰好由矩阵 $s$ 所表示；若存在，请构造出这样的一棵合法树。

$^\dagger$ 若顶点 $c$ 与顶点 $u$ 之间存在一条边，且 $c$ 不在从根到顶点 $u$ 的唯一简单路径上，则称顶点 $c$ 是顶点 $u$ 的一个子节点。

The first line contains a single integer $n$ ($1 \le n \le 5000$) — the number of vertices in the tree.

Each of the next $n$ lines contains a string with $n$ characters, the $j$-th character of the $i$-th line representing $s_{i, j}$ ($s_{i, j} \in {\mathtt{0}, \mathtt{1}}$) — the winning and losing states of the tree.

第一行包含一个整数 $n$（$1 \le n \le 5000$）——树中顶点的数量。

接下来的 $n$ 行，每行包含一个长度为 $n$ 的字符串；其中第 $i$ 行的第 $j$ 个字符表示 $s_{i, j}$（$s_{i, j} \in \{\mathtt{0}, \mathtt{1}\}$）——树的胜负状态。

If there is no tree satisfying the winning and losing states represented by matrix $s$, print a single line containing "NO".

Otherwise, if there exists a tree satisfying matrix $s$, print "YES" on the first line, followed by $n - 1$ lines each containing two integers $u$ and $v$ ($1 \le u, v \le n$) representing that the tree has an edge between vertices $u$ and $v$.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

If there are multiple trees satisfying the winning and losing states represented by matrix $s$, print any of them.

如果不存在满足矩阵 $s$ 所表示的胜负状态的树，则输出一行，内容为 "NO"。

否则，若存在满足矩阵 $s$ 的树，则第一行输出 "YES"，随后输出 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示该树中存在连接顶点 $u$ 和 $v$ 的一条边。

你可以以任意大小写形式输出答案（大写或小写均可）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均会被识别为肯定回答。

若存在多个满足矩阵 $s$ 所表示的胜负状态的树，输出其中任意一个即可。

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$.

在第一个测试用例中，路径图 $1\!-\!4\!-\!2\!-\!3$ 满足矩阵 $s$ 所表示的胜负状态。例如，$s_{3,3} = 1$，因为先手玩家可将硬币从 $3\rightarrow 2$ 移动，随后后手玩家将硬币从 $2\rightarrow 4$ 移动，最后先手玩家将硬币从 $4\rightarrow 1$ 移动。此时节点 $1$ 没有子节点，因此后手玩家无法进行下一步操作而失败。另一方面，$s_{1,3} = 0$，因为若以 $1$ 为根节点，则节点 $3$ 没有子节点，故先手玩家无法执行首次移动而失败。

在第二个测试用例中，可以证明：不存在任何树能满足矩阵 $s$ 所表示的胜负状态。