← 返回题目列表

Codeforces · 1710/D

D. 恢复树

中文机器翻译题面 查看原题

Rhodoks 有一颗有 $$$n$$$ 个顶点的树,但他不记得它的结构。顶点索引从 $$$1$$$ 到 $$$n$$$。

如果索引为 $$$l$$$, $$$l + 1$$$, ..., $$$r$$$ 的顶点在 Rhodoks 树中形成连通分量,则线段 $$$[l,r]$$$ ($$$1 \leq l \leq r \leq n$$$) 是好的。否则就不好了。

例如,如果树是图中的树,则只有 $$$[3,4]$$$ 段是坏的,而所有其他段都是好的。

对于每个 $$$\frac{n(n+1)}{2}$$$ 段,Rhodoks 都会记住它是好是坏。你能帮他找回那棵树吗?如果有多个解决方案,请打印其中一个。

保证至少有一棵树满足Rhodoks的描述。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2000$$$) — 树中的顶点数。

然后是 $$$n$$$ 行。这些行的第 $$$i$$$ 包含长度为 $$$n+1-i$$$ 的字符串 $$$n+1-i$$$,由 0 和 1 组成。如果段 $$$[i,i+j-1]$$$ 是好的,则 $$$good_i$$$ 的第 $$$j$$$ 字符为 1,否则 $$$good_i$$$ 的第 $$$j$$$ 字符为 0。

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

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

输出

对于每个测试用例,打印描述您恢复的树的 $$$n-1$$$ 行。

第 $$$i$$$ 行应包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i,v_i \leq n$$$),表示顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间的边。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

3
4
1111
111
10
1
6
111111
11111
1111
111
11
1
12
100100000001
11100000001
1000000000
100000000
10010001
1110000
100000
10000
1001
111
10
1

输出 #1

1 2
2 3
2 4
1 2
2 3
3 4
4 5
5 6
2 3
6 7
10 11
2 4
6 8
10 12
1 4
5 8
9 12
5 12
2 12

注意

第一个测试用例在语句中进行了解释。

在第二个测试用例中,一种可能的树如下:

在第三个测试用例中,一种可能的树如下: