Tree Recovery

题意翻译

### 题目描述 给定一棵 $n$ 个节点的树，节点编号为 $1\sim n$。 树的形态是未知的，但我们知道： * 所有边的边权都为 $1$。 * $n-1$ 行信息： * 第 $i$ 行信息由 $n-i$ 个以空格隔开的 $01$ 字符串组成。 * 定义 $d(x,y)$ 为树上 $x,y$ 两点之间的距离。我们约定字符串下标从 $1$开始。 * 对于第 $i$ 行的 第 $j$ 个字符串 $s$，$s_k=0$ 表示 $d(i,k)\neq d(i+j,k)$，$s_k=1$ 表示 $d(i,k)=d(i+j,k)$。 ### 输入格式 **本题有多组数据**。 * 第一行是一个整数 $t$，表示数据组数。 对于每组数据： * 第一行是一个整数 $n$，表示树的节点数量。 * 接下来 $n-1$ 行中的第 $i$ 行是 $n-i$ 个以空格隔开的 $01$ 字符串，意义见题目描述。 ### 输出格式 对于每组数据： * 如果不存在符合要求的树，输出一行，内容为一个字符串 `No`。 * 如果存在符合要求的树，输出 $n$ 行： * 第一行输出一个字符串 `Yes`。 * 接下来 $n-1$ 行，每行输出两个用空格隔开的整数 $x,y$，表示 $x$ 和 $y$ 之间有一条边。 * 如果符合要求的树的形态不唯一，你可以输出任何一种（原文没有提及边的输出顺序，但样例中是以 $x$ 为第一关键字，$y$ 为第二关键字的字典序升序）。 * 对 `Yes` 和 `No` 大小写不敏感，每个字母都可以以大写或小写输出。 ### 数据范围 对于所有测试点，$t\leqslant 200$，$n\leqslant 100$。 对于每个测试点的多组数据，至多有 $2$ 组数据的 $n>50$，至多有 $5$ 组数据的 $n>20$。

题目描述

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<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.

输入输出格式

输入格式

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>50 $ ; - there are at most $ 5 $ test cases that have $ n>20 $ .

输出格式

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).

输入输出样例

输入样例 #1

5
2
00
2
10
3
001 000
000
3
001 010
000
5
00000 01001 00000 01100
00000 10000 00000
00000 11010
00000

输出样例 #1

Yes
1 2
No
Yes
1 3
2 3
No
Yes
1 2
1 4
2 3
2 5

**Tree Recovery**

**题目描述：**
给定一个包含 $ n $ 个节点的树，节点编号为 $ 1 $ 到 $ n $。所有边的边权都是 $ 1 $。树的形态是未知的，但提供了 $ n-1 $ 行信息，每行包含 $ n-i $ 个长度为 $ n $ 的由 '0' 和 '1' 组成的字符串。字符串的第 $ k $ 个字符表示节点 $ i $ 和节点 $ k $ 之间的距离关系：若字符为 '0'，则表示 $ d(i, k) \neq d(i+j, k) $；若字符为 '1'，则表示 $ d(i, k) = d(i+j, k) $。需要恢复这棵树的结构，或者报告不存在满足条件的树。

**输入格式：**
输入包含多组测试用例。第一行是一个整数 $ t $，表示测试用例的数量。每个测试用例的第一行是一个整数 $ n $，表示树的节点数量。接下来 $ n-1 $ 行，每行的格式如题目描述。

**输出格式：**
对于每个测试用例，如果不存在符合要求的树，输出 `No`。如果存在，则首先输出 `Yes`，然后输出 $ n-1 $ 行，每行包含两个整数 $ x, y $，表示节点 $ x $ 和节点 $ y $ 之间有一条边。如果有多个解，可以输出任意一个。

**数据范围：**
$ t \leqslant 200 $，$ n \leqslant 100 $。在所有测试用例中，最多有两组数据的 $ n > 50 $，最多有五组数据的 $ n > 20 $。

**输入输出样例：**
**输入样例 #1：**
```
5
2
00
2
10
3
001 000
000
3
001 010
000
5
00000 01001 00000 01100
00000 10000 00000
00000 11010
00000
```
**输出样例 #1：**
```
Yes
1 2
No
Yes
1 3
2 3
No
Yes
1 2
1 4
2 3
2 5
```**Tree Recovery** **题目描述：** 给定一个包含 $ n $ 个节点的树，节点编号为 $ 1 $ 到 $ n $。所有边的边权都是 $ 1 $。树的形态是未知的，但提供了 $ n-1 $ 行信息，每行包含 $ n-i $ 个长度为 $ n $ 的由 '0' 和 '1' 组成的字符串。字符串的第 $ k $ 个字符表示节点 $ i $ 和节点 $ k $ 之间的距离关系：若字符为 '0'，则表示 $ d(i, k) \neq d(i+j, k) $；若字符为 '1'，则表示 $ d(i, k) = d(i+j, k) $。需要恢复这棵树的结构，或者报告不存在满足条件的树。 **输入格式：** 输入包含多组测试用例。第一行是一个整数 $ t $，表示测试用例的数量。每个测试用例的第一行是一个整数 $ n $，表示树的节点数量。接下来 $ n-1 $ 行，每行的格式如题目描述。 **输出格式：** 对于每个测试用例，如果不存在符合要求的树，输出 `No`。如果存在，则首先输出 `Yes`，然后输出 $ n-1 $ 行，每行包含两个整数 $ x, y $，表示节点 $ x $ 和节点 $ y $ 之间有一条边。如果有多个解，可以输出任意一个。 **数据范围：** $ t \leqslant 200 $，$ n \leqslant 100 $。在所有测试用例中，最多有两组数据的 $ n > 50 $，最多有五组数据的 $ n > 20 $。 **输入输出样例：** **输入样例 #1：** ``` 5 2 00 2 10 3 001 000 000 3 001 010 000 5 00000 01001 00000 01100 00000 10000 00000 00000 11010 00000 ``` **输出样例 #1：** ``` Yes 1 2 No Yes 1 3 2 3 No Yes 1 2 1 4 2 3 2 5 ```