#P18515. Flow 2

Flow 2

Flow 2

Little Cyan Fish 和他的队友、北京大学的 Qingyu Xiao 正在上算法课。他们正在阅读 Maximum Flow and Minimum-Cost Flow in Almost-Linear Time 与 All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time。Little Cyan Fish 对最大流很感兴趣,希望你帮助解决一个相关问题。先回顾几个基本概念。

没有重边、没有自环的无向图 G=(V,E) 称为简单图。所有边的容量均为1,即图中的边都没有权值。

对两个不同的顶点 s,t,分别把它们称为源点和汇点。流为边上非负流量的分配(沿所使用的方向记作 f_uv),需要满足:

  • 容量限制:每条边的流量不超过1,即 0≤f_uv≤1;
  • 流量守恒:除 s,t 以外,任意顶点的流入量等于流出量,即
$$\forall v\in V\setminus\{s,t\}:\quad \sum_{u:(u,v)\in E}f_{uv}=\sum_{u:(v,u)\in E}f_{vu}.$$

流的值是从源点送到汇点的流量,形式上为

$$|f|=\sum_{v:(s,v)\in E}f_{sv}=\sum_{u:(u,t)\in E}f_{ut}.$$

所有可行流中最大的流值记为 maxflow(s,t)。特别定义 maxflow(u,u)=0。无向边按通常的无向单位容量最大流理解,沿相反方向的流可以抵消。

现在,给出一张有 n 个顶点的无向简单图 G,顶点编号为1到n,计算矩阵 A=F(G),其中 A_uv=maxflow(u,v),是课程中的一道作业。Little Cyan Fish 认为这很直接,于是想研究逆问题:给定矩阵 A,构造一个无向简单图 G,使 F(G)=A。

一般的矩阵很难处理,所以本题保证矩阵的每个元素只可能是0、1、2、3。你能构造这样的图,或者判断不存在吗?

输入格式

第一行一个整数 T(1≤T≤1000),表示测试用例个数。

对每个测试用例:

  • 第一行一个整数 n(1≤n≤300);
  • 接下来 n 行,每行 n 个整数,第 i 行描述 A_i1,…,A_in;
  • 保证所有元素满足0≤A_ij≤3。

保证同一输入文件中所有测试用例的 n² 之和不超过 9×10^6。输入不保证对称、对角为0或者存在对应的图。

输出格式

对每个测试用例,若不存在满足 F(G)=A 的图,输出一行 No。

否则先输出一行 Yes,下一行输出所用边数 m,随后 m 行各输出两个整数 x,y,表示一条连接顶点 x,y 的无向边。输出图必须是无向简单图,不能有重边或自环,顶点仍为1到n。

若有多种合法方案,输出任意一种。

完整原样例

输入:

4
4
0 3 2 2
3 0 2 2
2 2 0 2
2 2 2 0
8
0 2 2 0 0 1 1 1
2 0 2 0 0 1 1 1
2 2 0 0 0 1 1 1
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
1 1 1 0 0 0 2 2
1 1 1 0 0 2 0 2
1 1 1 0 0 2 2 0
3
0 1 2
1 2 3
2 3 1
12
0 2 2 2 2 2 2 2 2 1 1 1
2 0 2 2 2 2 2 2 2 1 1 1
2 2 0 2 2 2 2 2 2 1 1 1
2 2 2 0 2 2 2 2 2 1 1 1
2 2 2 2 0 2 2 2 2 1 1 1
2 2 2 2 2 0 2 2 2 1 1 1
2 2 2 2 2 2 0 2 2 1 1 1
2 2 2 2 2 2 2 0 2 1 1 1
2 2 2 2 2 2 2 2 0 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 0

输出(其中一种方案):

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

原样例说明

第一个测试用例的一种可行图如下。

原题第一个测试用例的可行图

以 A_12=3 为例,下面的图展示了流值3的最大流,满足 maxflow(1,2)=3。

原题从1到2的三条流路径

第二个测试用例的一种可行图如下。

原题第二个测试用例的可行图

第三个测试用例显然没有满足所有 A_uu=0,因此不存在对应图。