• 来源：48th Petrozavodsk Programming Camp, Winter 2025, Day 2: National Taiwan U Contest，Problem J
• 原题名：Judge Error
• 时间限制：2 秒
• 空间限制：1024 MiB

题目描述

某场本地程序设计竞赛曾经发生过一次令人难忘的事故。出题人达里安设计了一道构造题：给定 $N$，要求构造一个含 $N$ 个顶点的简单无向图，使得图中恰好存在一个完美匹配，并且在这个条件下边数尽可能多。两个完美匹配若使用的边集合不同，则认为它们不同。

当时，另一位出题人贝尔说服达里安相信存在一个 $O(N^3)$ 的校验算法，于是数据范围被设到了 $N\le 500$。临近封题时，贝尔才发现那个算法并不正确，校验器可能需要 $O(N^4)$。达里安虽然改写了校验器，却没有降低数据范围，因为测试时似乎跑得还够快。

正式比赛中，某份提交让这个校验器运行了十几秒，最终触发了评测系统错误。现在，评测组希望你写出一个更快、更可靠的校验程序；同时，我们把问题推广到 $N\le 2000$。

给定一个简单无向图的邻接矩阵，请判断它是否恰好包含一个完美匹配。如果是，请输出这个唯一的完美匹配；否则输出 No。

输入格式

第一行包含一个整数 $N$，表示顶点数量。

接下来 $N$ 行，第 $i$ 行包含一个长度为 $N$ 的二进制字符串

这些字符串共同描述图：当且仅当 $g_{i,j}=1$ 时，顶点 $i$ 与顶点 $j$ 之间有边。

输出格式

如果给定图不恰好包含一个完美匹配，输出一行：

No

否则，第一行输出：

Yes

接下来输出 $\frac{N}{2}$ 行，第 $i$ 行输出两个整数 $u_i,v_i$，表示匹配中的一条边，并满足 $1\le u_i<v_i\le N$。

若存在唯一完美匹配，请按照

的顺序输出这些匹配边。

数据范围

• $2\le N\le 2000$；
• $N$ 为偶数；
• 对所有 $i$，有 $g_{i,i}=0$；
• 对所有 $i,j$，有 $g_{i,j}=g_{j,i}$；
• 输入图为简单无向图。

样例 1

输入

4
0100
1010
0101
0010

输出

Yes
1 2
3 4

样例 2

输入

4
0101
1010
0101
1010

输出

No