CF1710D.Recover the Tree

Rhodoks has a tree with $n$ vertices, but he doesn't remember its structure. The vertices are indexed from $1$ to $n$.

A segment $[l,r]$ ($1 \leq l \leq r \leq n$) is good if the vertices with indices $l$, $l + 1$, ..., $r$ form a connected component in Rhodoks' tree. Otherwise, it is bad.

For example, if the tree is the one in the picture, then only the segment $[3,4]$ is bad while all the other segments are good.

For each of the $\frac{n(n+1)}{2}$ segments, Rhodoks remembers whether it is good or bad. Can you help him recover the tree? If there are multiple solutions, print any.

It is guaranteed that the there is at least one tree satisfying Rhodoks' description.

罗多克斯有一棵包含 $n$ 个顶点的树，但他不记得其具体结构了。这些顶点编号为 $1$ 到 $n$。

若编号为 $l, l+1, \dots, r$（其中 $1 \leq l \leq r \leq n$）的顶点在罗多克斯的树中构成一个连通块，则称区间 $[l,r]$ 是好的；否则称为坏的。

例如，若树的结构如图所示，则只有区间 $[3,4]$ 是坏的，其余所有区间均为好的。

对于全部 $\frac{n(n+1)}{2}$ 个区间，罗多克斯都记得每个区间是好还是坏。你能帮他还原出这棵树吗？如果存在多种可能的解，输出任意一种即可。

题目保证至少存在一棵满足罗多克斯描述的树。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 1000$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2000$) — the number of vertices in the tree.

Then $n$ lines follow. The $i$-th of these lines contains a string $good_i$ of length $n+1-i$ consisting of 0 and 1. If the segment $[i,i+j-1]$ is good then the $j$-th character of $good_i$ is 1, otherwise $j$-th character of $good_i$ is 0.

It is guaranteed that the there is at least one tree consistent with the given data.

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

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

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2000$）——表示树中顶点的数量。

接下来是 $n$ 行。其中第 $i$ 行包含一个长度为 $n+1-i$ 的字符串 $good_i$，该字符串仅由字符 0 和 1 组成。若区间 $[i,i+j-1]$ 是“好”的，则 $good_i$ 的第 $j$ 个字符为 1；否则为 0。

保证至少存在一棵树与给定数据一致。

保证所有测试用例中 $n$ 的总和不超过 $2000$。

For each test case, print $n-1$ lines describing the tree you recover.

The $i$-th line should contain two integers $u_i$ and $v_i$ ($1 \leq u_i,v_i \leq n$), denoting an edge between vertices $u_i$ and $v_i$.

If there are multiple solutions, print any.

对于每个测试用例，输出 $n-1$ 行，描述你恢复出的树。

第 $i$ 行应包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i,v_i \leq n$），表示顶点 $u_i$ 与 $v_i$ 之间的一条边。

若存在多种解，输出任意一种即可。

The first test case is explained in the statement.

In the second test case, one possible tree is as follows:

In the third test case, one possible tree is as follows:

第一个测试用例已在题目描述中说明。

在第二个测试用例中，一种可能的树如下所示：

在第三个测试用例中，一种可能的树如下所示：