首先每个点至少要有两条边连接
那么容易想到先保证这一点然后再慢慢加边
那么先构成一个环即可：$(1,2),(2,3),(3,4)...(n,1)$
然后考虑加边，发现一个点加一条边还是合法的，那么不妨直接 $(1,4),(2,5),(3,6)$ ，然后一旦边数为质数了就直接输出答案
那么现在问题就是能否保证在 $[n,n+\left \lfloor \frac {n-3} {2} \right \rfloor]$ 范围内一定有质数
打个表发现在 $n \in [3,1000]$ 内唯一不合法的只有 $n=4$，那么特判一下就行了......
官方题解竟然也是这个操作？？？没有证明的吗？？？
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return x*f;
}
const int N=1e5+7;
int n,m;
struct edge {
int u,v;
edge (int _u=0,int _v=0) { u=_u,v=_v; }
};
vector <edge> ans;
inline void ins(int u,int v) { ans.push_back(edge(u,v)); }
int pri[N],tot;
bool not_pri[N];
void pre()
{
not_pri[1]=1;
for(int i=2;i<=2*n;i++)
{
if(!not_pri[i]) pri[++tot]=i;
for(int j=1;j<=tot;j++)
{
ll g=1ll*i*pri[j]; if(g>2*n) break;
not_pri[g]=1; if(i%pri[j]==0) break;
}
}
}
int main()
{
n=read(); pre();
for(int i=2;i<=n;i++) ins(i,i-1);
ins(1,n); int now=n;
if(n==4) ins(1,3),now++;
else
for(int i=1;i<=n-3;i++)
{
if(!not_pri[now]) break;
if(i&1) ins(i,i+3),now++;
}
if(not_pri[now]) { printf("-1\n"); return 0; }
printf("%d\n",now);
for(auto E: ans) printf("%d %d\n",E.u,E.v);
return 0;
}