#P18503. Isomorphic Delight

Isomorphic Delight

Isomorphic Delight

给定整数 nn,请构造一个有 nn 个顶点的简单无向图,要求该图是非对称的,并且在满足这些要求的所有图中,边数最少。如果不存在这样的图,输出不存在。

非对称的含义是:除了恒等置换之外,不存在任何顶点重新编号,使得到的图与原图完全相同。形式化地,对于图 G=(V,E)G=(V,E),不存在非恒等的顶点置换 π\pi,使得对于任意两个顶点 u,vu,v,都有

$$uv\in E\quad\Longleftrightarrow\quad \pi(u)\pi(v)\in E.$$

简单图不允许自环或重复的无向边。图可以不连通;全部 nn 个顶点(包括孤立点)都属于所构造的图。输出使用编号 11 到 nn。

输入格式

第一行也是唯一一行包含一个整数 nn(1≤n≤1061\le n\le 10^6),表示图的顶点数。

输出格式

如果存在这样的非对称图,首先输出 YES;否则输出 NO。

输出 YES 时,下一行输出一个整数 mm,表示所构造图的边数。接下来的 mm 行,每行输出两个整数 u,vu,v,表示一条连接顶点 u,vu,v 的无向边。任何无向边都不能出现两次,图必须非对称,且 mm 必须是所有合法图中最小的边数。可以输出任意一种最优方案。

原样例 1

1
YES
0

原样例 2

6
YES
6
1 2
2 3
1 3
3 4
2 5
5 6

原样例 3

4
NO