CF1710D Recover the Tree

Rhodoks 有一棵包含 $n$ 个顶点的树，但他已经不记得这棵树的结构了。顶点编号从 $1$ 到 $n$。 如果区间 $[l, r]$（$1 \leq l \leq r \leq n$）中的顶点 $l, l+1, \ldots, r$ 在 Rhodoks 的树中构成一个连通块，则称该区间是好的，否则称为坏的。 例如，如果树的结构如图所示，则只有区间 $[3,4]$ 是坏的，其余所有区间都是好的。  对于每一个 $\frac{n(n+1)}{2}$ 个区间，Rhodoks 都记得它是好还是坏。你能帮他还原这棵树吗？如果有多种方案，输出任意一种即可。 保证至少存在一棵树满足 Rhodoks 的描述。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试数据的组数。 每组测试数据的第一行包含一个整数 $n$（$1 \leq n \leq 2000$），表示树的顶点数。 接下来 $n$ 行，每行一个长度为 $n+1-i$ 的字符串 $good_i$，仅包含 $0$ 和 $1$。如果区间 $[i, i+j-1]$ 是好区间，则 $good_i$ 的第 $j$ 个字符为 $1$，否则为 $0$。 保证至少存在一棵树与给定数据一致。 保证所有测试数据中 $n$ 的总和不超过 $2000$。

对于每组测试数据，输出 $n-1$ 行，每行两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示树中的一条边。 如果有多种方案，输出任意一种。

第一个测试点的解释见题面。 第二个测试点，一种可能的树结构如下：  第三个测试点，一种可能的树结构如下：  由 ChatGPT 4.1 翻译