311003: CF1919G. Tree LGM
Description
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$.
InputThe 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.
OutputIf 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.
ExamplesInput4 1100 0101 0011 0101Output
YES 4 1 3 2 2 4Input
3 001 010 100Output
NONote
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$.
Output
在TreeWorld中，有一个在树上进行的双人游戏，树有n个从1到n标记的顶点。游戏的规则是：首先选择一个顶点作为树的根，然后在另一个顶点（可能是根顶点）上放置一枚硬币。然后，每个玩家轮流将硬币移动到硬币当前所在的顶点的任意子顶点。第一个无法进行移动的玩家输掉游戏。
Alice想要成为树LGM，因此她花了很多时间研究这个游戏。她记录了一个n×n的矩阵s，其中s[i,j]=1表示如果选择顶点i作为树的根，且硬币最初放在顶点j上，则第一个玩家能赢。否则，s[i,j]=0。Alice是个完美主义者，她假设游戏中两个玩家都会完美地进行游戏。
但是，她在去比赛的路上不小心撞到了头，忘记了树的样子。需要判断是否存在一个树满足由矩阵s表示的胜负状态，如果存在，则构建一个有效的树。
输入输出数据格式：
输入：
- 第一行包含一个整数n（1≤n≤5000）——树中的顶点数。
- 接下来的n行，每行包含一个长度为n的字符串，代表矩阵s的行，其中第i行第j个字符代表s[i,j]（s[i,j]∈{0,1}）——树的胜负状态。
输出：
- 如果不存在满足矩阵s表示的胜负状态的树，则打印一行“NO”。
- 如果存在满足矩阵s的树，则在第一行打印“YES”，然后是n-1行，每行包含两个整数u和v（1≤u,v≤n），表示树在顶点u和v之间有一条边。
- 如果有多棵树满足矩阵s表示的胜负状态，则输出其中任意一棵。
示例：
输入：
4
1100
0101
0011
0101
输出：
YES
4 1
3 2
2 4
输入：
3
001
010
100
输出：
NO
注意：
在第一个测试案例中，线图1-4-2-3满足矩阵s表示的胜负状态。例如，s[3,3]=1，因为第一个玩家可以从3→2移动硬币，然后第二个玩家从2→4移动硬币，最后第一个玩家从4→1移动硬币。此时，1没有子顶点，所以第二个玩家无法进行移动并输掉游戏。另一方面，s[1,3]=0，因为如果1是根，那么3没有子顶点，所以第一个玩家无法进行第一次移动并输掉游戏。
在第二个测试案例中，可以证明没有树满足矩阵s表示的胜负状态。题目大意： 在TreeWorld中，有一个在树上进行的双人游戏，树有n个从1到n标记的顶点。游戏的规则是：首先选择一个顶点作为树的根，然后在另一个顶点（可能是根顶点）上放置一枚硬币。然后，每个玩家轮流将硬币移动到硬币当前所在的顶点的任意子顶点。第一个无法进行移动的玩家输掉游戏。 Alice想要成为树LGM，因此她花了很多时间研究这个游戏。她记录了一个n×n的矩阵s，其中s[i,j]=1表示如果选择顶点i作为树的根，且硬币最初放在顶点j上，则第一个玩家能赢。否则，s[i,j]=0。Alice是个完美主义者，她假设游戏中两个玩家都会完美地进行游戏。 但是，她在去比赛的路上不小心撞到了头，忘记了树的样子。需要判断是否存在一个树满足由矩阵s表示的胜负状态，如果存在，则构建一个有效的树。 输入输出数据格式： 输入： - 第一行包含一个整数n（1≤n≤5000）——树中的顶点数。 - 接下来的n行，每行包含一个长度为n的字符串，代表矩阵s的行，其中第i行第j个字符代表s[i,j]（s[i,j]∈{0,1}）——树的胜负状态。 输出： - 如果不存在满足矩阵s表示的胜负状态的树，则打印一行“NO”。 - 如果存在满足矩阵s的树，则在第一行打印“YES”，然后是n-1行，每行包含两个整数u和v（1≤u,v≤n），表示树在顶点u和v之间有一条边。 - 如果有多棵树满足矩阵s表示的胜负状态，则输出其中任意一棵。 示例： 输入： 4 1100 0101 0011 0101 输出： YES 4 1 3 2 2 4 输入： 3 001 010 100 输出： NO 注意： 在第一个测试案例中，线图1-4-2-3满足矩阵s表示的胜负状态。例如，s[3,3]=1，因为第一个玩家可以从3→2移动硬币，然后第二个玩家从2→4移动硬币，最后第一个玩家从4→1移动硬币。此时，1没有子顶点，所以第二个玩家无法进行移动并输掉游戏。另一方面，s[1,3]=0，因为如果1是根，那么3没有子顶点，所以第一个玩家无法进行第一次移动并输掉游戏。 在第二个测试案例中，可以证明没有树满足矩阵s表示的胜负状态。