CF1696F.Tree Recovery

Fishingprince loves trees. A tree is a connected undirected graph without cycles.

Fishingprince has a tree of $n$ vertices. The vertices are numbered $1$ through $n$. Let $d(x,y)$ denote the shortest distance on the tree from vertex $x$ to vertex $y$, assuming that the length of each edge is $1$.

However, the tree was lost in an accident. Fortunately, Fishingprince still remembers some information about the tree. More specifically, for every triple of integers $x,y,z$ ($1\le x \lt y\le n$, $1\le z\le n$) he remembers whether $d(x,z)=d(y,z)$ or not.

Help him recover the structure of the tree, or report that no tree satisfying the constraints exists.

Fishingprince 非常喜欢树。树是一种无环的连通无向图。

Fishingprince 拥有一棵包含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。记 $d(x,y)$ 表示树上顶点 $x$ 到顶点 $y$ 的最短距离（假设每条边的长度均为 $1$）。

然而，这棵树在一次事故中丢失了。幸运的是，Fishingprince 仍记得关于该树的一些信息。具体而言，对于每个三元组整数 $(x,y,z)$（满足 $1\le x \lt y\le n$ 且 $1\le z\le n$），他记得 $d(x,z)=d(y,z)$ 是否成立。

请帮助他恢复该树的结构；若不存在满足所有约束条件的树，则报告无解。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 200$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($2\le n\le 100$) — the number of vertices in the tree.

Then $n-1$ lines follow. The $i$-th line of these $n-1$ lines contains $n-i$ strings of length $n$ consisting of 0 and 1. If the $k$-th character in the $j$-th string of the $i$-th line is 0, it means that $d(i,k)\ne d(i+j,k)$; if the $k$-th character in the $j$-th string of the $i$-th line is 1, it means that $d(i,k)=d(i+j,k)$.

It is guaranteed that in one input file,

• there are at most $2$ test cases that have $n \gt 50$;
• there are at most $5$ test cases that have $n \gt 20$.

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

每个测试用例的第一行包含一个整数 $n$（$2\le n\le 100$）——树中顶点的数量。

接下来是 $n-1$ 行。这 $n-1$ 行中的第 $i$ 行包含 $n-i$ 个长度为 $n$ 的字符串，每个字符串仅由字符 0 和 1 组成。若第 $i$ 行中第 $j$ 个字符串的第 $k$ 个字符为 0，表示 $d(i,k)\ne d(i+j,k)$；若该字符为 1，则表示 $d(i,k)=d(i+j,k)$。

保证在单个输入文件中：

• 满足 $n \gt 50$ 的测试用例至多有 $2$ 个；
• 满足 $n \gt 20$ 的测试用例至多有 $5$ 个。

For each test case:

• if no answer exists, output No;
• otherwise, on the first line output Yes. Then output $n-1$ lines. Each line should contain two integers $x,y$ ($1\le x,y\le n$), denoting an edge between vertices $x$ and $y$ of the tree. If there are multiple solutions, print any.

When printing Yes and No, you can print each letter in any case (upper or lower).

对于每个测试用例：

• 如果不存在答案，输出 No；
• 否则，在第一行输出 Yes。然后输出 $n-1$ 行，每行包含两个整数 $x,y$（$1\le x,y\le n$），表示树中顶点 $x$ 与 $y$ 之间的一条边。如果存在多个解，输出任意一个即可。

在输出 Yes 和 No 时，每个字母可以使用任意大小写（大写或小写）。