CF2208D1.Tree Orientation (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, the constraint on $n$ is lower. You can hack only if you solved all versions of this problem.

You once had an undirected tree with $n$ nodes. To make the tree look more interesting, you decided to assign an arbitary direction to each of the $n-1$ edges.

As time goes by, you forgot the structure of your tree. However, you found a note which recorded after the direction of the edges have been assigned, whether $u$ can reach $v$$^{\text{∗}}$ for all ordered pairs of $(u,v)$ which satisfies $1\le u,v\le n$.

You want to find out the structure of the tree and the direction of the edges from the information given by the note. Determine if there is possible solution and construct one. If there are multiple solutions, you only need to find one of them.

$^{\text{∗}}$For a directed graph, we say that $x$ can reach $y$ if and only if there exists a sequence of nodes $u_1,u_2,\ldots,u_k$ such that $u_1=x,u_k=y$ and for all $i$ from $2$ to $k$, the directed edge $u_{i-1}\rightarrow u_i$ exists. In particular, a node can always reach itself.

这是该问题的简单版本。两个版本的区别在于，本版本中对 $n$ 的约束更小。仅当您解决了该问题的所有版本时，才可进行 Hack。

你曾经拥有一棵包含 $n$ 个节点的无向树。为了让这棵树看起来更有趣，你决定为它的 $n-1$ 条边任意指定一个方向。

随着时间推移，你忘记了这棵树的原始结构。然而，你发现了一张笔记，其中记录了在所有边被赋予方向之后，对所有满足 $1 \le u, v \le n$ 的有序对 $(u, v)$，节点 $u$ 是否能够到达节点 $v$$^{\text{∗}}$。

你想根据这张笔记所给的信息，还原出原树的结构以及各边的方向。请判断是否存在可行解，并构造出一个可行解。若存在多个可行解，你只需给出其中一个即可。

$^{\text{∗}}$ 对于有向图，我们称 $x$ 可以到达 $y$，当且仅当存在一个节点序列 $u_1, u_2, \ldots, u_k$，使得 $u_1 = x$、$u_k = y$，且对每个从 $2$ 到 $k$ 的 $i$，均存在有向边 $u_{i-1} \rightarrow u_i$。特别地，每个节点总能到达其自身。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test cases contain an integer $n$ ($2\le n\le 500$) denoting the number of nodes your tree have.

The following $n$ lines contain a string $s_i$. $s_i$ is of length $n$ and consists only of $0$ and $1$. The $j$-th character of $s_i$ is $1$ if and only if $i$ can reach $j$ after the edges are directed.

It is guaranteed that the sum of $n^3$ over all test cases does not exceed $500^3$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\le n\le 500$），表示树中节点的数量。

接下来的 $n$ 行，每行包含一个字符串 $s_i$。$s_i$ 的长度为 $n$，且仅由字符 $0$ 和 $1$ 组成。$s_i$ 的第 $j$ 个字符为 $1$ 当且仅当在将边定向后，节点 $i$ 可以到达节点 $j$。

保证所有测试用例的 $n^3$ 之和不超过 $500^3$。

For each testcase, output $\texttt{Yes}$ if a solution exists, otherwise print $\texttt{No}$. If the answer is $\texttt{Yes}$, on the following lines output a description of the edges constructed.

Output $n-1$ lines denoting the directed edges. Each line should contain two integers $x$ and $y$, denoting that after the edges are directed, the directed edge $x\rightarrow y$ exists. If there are multiple solutions, print any of them.

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.

对于每个测试用例，若存在解，则输出 $\texttt{Yes}$；否则输出 $\texttt{No}$。若答案为 $\texttt{Yes}$，则在接下来的行中输出所构造边的描述。

输出 $n-1$ 行，每行表示一条有向边。每行应包含两个整数 $x$ 和 $y$，表示在对边进行定向后，存在有向边 $x\rightarrow y$。若存在多种解，输出任意一种即可。

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

For the first test case, nodes $1$ and $4$ can only reach themselves, node $2$ can reach every node, node $3$ can only reach node $1$ and $3$. The constructed edges satisfy this constraint.

For the second test case, it can be proven that no possible solution exists.

对于第一个测试用例，节点 $1$ 和 $4$ 只能到达自身，节点 $2$ 可以到达所有节点，节点 $3$ 只能到达节点 $1$ 和 $3$。所构造的边满足该约束条件。

对于第二个测试用例，可以证明不存在可行解。