#P18384. DFS Order 6

DFS Order 6

DFS Order 6

题目描述

给定一个有 nn 个顶点的连通无向简单图 GG,顶点编号为 1,2,…,n1,2,\ldots,n,以及起点 ss。按照下面的规则进行深度优先搜索:

DFS(x):
    标记 x 已访问
    将 x 加入访问顺序
    按顶点编号从小到大枚举 x 的所有相邻顶点 y:
        若 y 尚未访问:
            DFS(y)

Generate(G, s):
    将所有顶点标记为尚未访问
    清空访问顺序
    DFS(s)
    返回访问顺序

每个顶点只在第一次访问时加入顺序。由于总是按编号升序枚举邻居,固定图和起点后,这个 DFS 顺序唯一确定。

七个顶点、七条边的示例图

上图有 77 个顶点和 77 条边。从顶点 11 出发的 DFS 顺序为 [1,2,3,7,4,5,6][1,2,3,7,4,5,6]。

现在给出 nn 个排列 a1,a2,…,ana_1,a_2,\ldots,a_n。其中 aia_i 声称是从顶点 ii 出发得到的 DFS 顺序。

请构造任意一个顶点为 1,2,…,n1,2,\ldots,n 的连通无向简单图,使从每个顶点 ii 出发的 DFS 顺序都恰好为 aia_i;或者判断不存在这样的图。

简单图不允许自环和重边。

输入格式

输入包含多组测试数据。第一行包含整数 TT(T≥1T\ge1)。

对于每组测试数据:

第一行包含一个整数 nn(1≤n≤2001\le n\le200)。

接下来 nn 行,第 ii 行包含 nn 个整数 ai,1,ai,2,…,ai,na_{i,1},a_{i,2},\ldots,a_{i,n}。保证这一行是 1,2,…,n1,2,\ldots,n 的一个排列,并且 ai,1=ia_{i,1}=i。

保证所有测试数据的 n2n^2 之和不超过 4×1044\times10^4。

输出格式

对每组测试数据:

如果不存在满足要求的图,输出一行 No。

否则第一行输出 Yes,第二行输出边数 mm,其中

n−1≤m≤n(n−1)2.n-1\le m\le\frac{n(n-1)}2.

接下来 mm 行,每行输出两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n,u≠vu\ne v),表示图中的一条无向边。

输出的图必须简单、连通,并且从每个起点得到的 DFS 顺序都与输入一致。可以输出任意一种符合要求的图,边的输出顺序及每条边两个端点的输出顺序均不限。

当 n=1n=1 时,合法图的边数为 00。

样例输入

2
3
1 2 3
2 1 3
3 2 1
3
1 2 3
2 3 1
3 1 2

样例输出

Yes
2
1 2
2 3
No

样例说明

第一组数据中,路径 1−2−31-2-3 是一种合法构造。从三个起点分别得到 [1,2,3][1,2,3]、[2,1,3][2,1,3]、[3,2,1][3,2,1]。

第二组数据中,不存在符合要求的图。