人人人所周知，随机化好写且不好卡

一种方法是构造一种唯一的完美匹配，且边数为 $n^2$ 的即可

那么构造一个桥，且两边的大小都是奇数，除去桥和桥边上的两个点，剩下的可以递归构造

容易证明，这一定有完美匹配，且唯一

以下是generator

#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
inline int myrnd(int x){return rnd()%x;}
int xx[1000005],yy[1000005],cnt;
void add(int x,int y){
    xx[++cnt]=x;yy[cnt]=y;
}
void gen(int x,int y){
    if(x==0)return ;
    int now=rnd()%(x>>1);
    add(1+y,now*2+2+y);
    for(int i=1;i<=now*2;i++)
        add(1+y,1+i+y);
    for(int i=now*2+3;i<=x;i++)
        add(now*2+2+y,i+y);
    gen(now*2,y+1);
    gen(x-now*2-2,now*2+2+y);
}
int n=500,id[1000005];
int main(){
    freopen("a.in","w",stdout);
    gen(n,0);for(int i=1;i<=cnt;i++)id[i]=i;
    random_shuffle(id+1,id+cnt+1,myrnd);
    printf("%d %d\n",n,cnt);
    for(int i=1;i<=cnt;i++)
        printf("%d %d\n",xx[id[i]],yy[id[i]]);
}