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

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

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