在 TreeWorld 中,有一种流行的两人游戏,在一棵树上玩,$$$n$$$ 顶点标记为 $$$1$$$ 到 $$$n$$$。在这个游戏中,锦标赛领导者首先选择一个顶点作为树的根,然后选择另一个顶点(可能与根相同的顶点)来放置硬币。然后,每个玩家轮流将硬币移动到硬币当前所在顶点的任何子$$$^\dagger$$$。第一个无法采取行动的玩家失败。
Alice想成为树LGM,所以她花了很多时间研究游戏。她写下了一个 $$$n$$$ by $$$n$$$ 矩阵 $$$s$$$,其中 $$$s_{i,j} = \mathtt{1}$$$ 如果第一个玩家可以获胜,树根被选为顶点 $$$i$$$,并且硬币最初放置在顶点 $$$j$$$ 上。否则,$$$s_{i, j} = \mathtt{0}$$$。 Alice 是一个完美主义者,所以她假设两个玩家在游戏中都玩得很完美。
然而,她在去比赛的路上不小心撞到了头,忘记了那棵树是什么样子。判断是否存在满足矩阵$$$s$$$表示的胜负状态的树,如果存在则构造有效的树。
$$$^\dagger$$$ 如果 $$$c$$$ 和 $$$u$$$ 之间存在边,并且 $$$c$$$ 不在从根到顶点 $$$u$$$ 的唯一简单路径上,则顶点 $$$c$$$ 是顶点 $$$u$$$ 的子节点。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 树中的顶点数。
接下来的 $$$n$$$ 行包含一个包含 $$$n$$$ 个字符的字符串,第 $$$i$$$ 行的第 $$$j$$$ 个字符代表 $$$s_{i, j}$$$ ($$$s_{i, j} \in \{\mathtt{0}, \mathtt{1}\}$$$) — 获胜者和失败者树的状态。
输出
如果没有树满足矩阵 $$$s$$$ 表示的获胜和失败状态,则打印包含“NO”的单行。
否则,如果存在满足矩阵 $$$s$$$ 的树,则在第一行打印“YES”,后面是 $$$n - 1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$) 表示该树在顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
如果有多棵树满足矩阵 $$$s$$$ 表示的获胜和失败状态,则打印其中任何一个。
示例
输入 #1
4 1100 0101 0011 0101
输出 #1
YES 4 1 3 2 2 4
输入 #2
3 001 010 100
输出 #2
NO
注意
在第一个测试用例中,线图 $$$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$$$ 表示的获胜和失败状态。