#P18503. Isomorphic Delight
Isomorphic Delight
Isomorphic Delight
给定整数 ,请构造一个有 个顶点的简单无向图,要求该图是非对称的,并且在满足这些要求的所有图中,边数最少。如果不存在这样的图,输出不存在。
非对称的含义是:除了恒等置换之外,不存在任何顶点重新编号,使得到的图与原图完全相同。形式化地,对于图 ,不存在非恒等的顶点置换 ,使得对于任意两个顶点 ,都有
$$uv\in E\quad\Longleftrightarrow\quad \pi(u)\pi(v)\in E.$$简单图不允许自环或重复的无向边。图可以不连通;全部 个顶点(包括孤立点)都属于所构造的图。输出使用编号 到 。
输入格式
第一行也是唯一一行包含一个整数 (),表示图的顶点数。
输出格式
如果存在这样的非对称图,首先输出 YES;否则输出 NO。
输出 YES 时,下一行输出一个整数 ,表示所构造图的边数。接下来的 行,每行输出两个整数 ,表示一条连接顶点 的无向边。任何无向边都不能出现两次,图必须非对称,且 必须是所有合法图中最小的边数。可以输出任意一种最优方案。
原样例 1
1
YES
0
原样例 2
6
YES
6
1 2
2 3
1 3
3 4
2 5
5 6
原样例 3
4
NO