考虑一个构造，对于坐标$(x,y)$，连一条$x$到$y$的边（注意：横坐标和纵坐标即使权值相同也是不同的点），之后每一个连通块独立，考虑一个连通块内部：

每一个点意味着一次删除操作，每一个边意味着一个坐标，由于每一次操作最多删除一个点，因此首先点数要大于等于边数，同时总边数=总点数=$2n$，因此每一个连通块都是基环树

考虑叶子，其必然要删除一个点，只能是与其相连的边，重复此过程，对于不在环上的点或边都可以确定删除的配对关系，对于环上的点枚举两种方向也可以确定

接下来，就是要对于一组给定的配对关系，求对应的方案数，然后相加即为该连通块的方案数

再建一张新图，点仍然是操作，边是有向边，表示操作的先后顺序，考虑如何建图：

1.如果操作$x_{1}$消除了$(x,y)$，那么所有$(x,y')$（其中$y'<y$）都应在其之前被删除，即删除这些点的操作要在$(x,y)$之前，更具体的，将与$x$相连且比$y$小的点向$x$连边

2.同时，我们要保证$(x,y)$不被$y_{2}$删除，但这个的充分条件为$y_{2}$删除了$(x',y)$，而根据上述的边也满足了此条件，因此不必考虑

对于新图，统计方案数：如果存在环，那么方案数为0，否则必然是一棵内向树森林（因为每一个点至多向其父亲连边），考虑dp

令$f_{i}$表示以$i$为根的子树的方案数，由于根必须是子树中最早删除的节点，令$sz_{i}$表示$i$子树大小，$V$表示总点数，则有$ans=\frac{V!}{\prod sz_{i}}$

（可以这么看待这个式子：对于所有排列中，对于$i$其在子树内删除的名次是随机的，而只有是子树中第一个被删除才符合条件，因此是$\frac{1}{sz_{i}}$种）

假设一个连通块点数为$V_{i}$，方案数为$S_{i}$，不难得到$ans=\frac{(2n)!}{\prod V_{i}!}\prod S_{i}$，计算即可

1 #include
2 using namespace std;
3 #define N 200005
4 #define mod 1000000007
5 struct ji{
6 int nex,to;
7 }edge[N<<1]; 8 vectorv,g[N];
9 int E,n,x,y,tot,ans,head[N],vis[N],f[N],p[N],r[N],sz[N],fac[N],inv[N];
10 void add(int x,int y){
11 edge[E].nex=head[x];
12 edge[E].to=y;
13 head[x]=E++;
14 }
15 void dfs(int k,int fa){
16 f[k]=p[k]=fa;
17 vis[k]=1;
18 v.push_back(k);
19 for(int i=head[k];i!=-1;i=edge[i].nex)
20 if (edge[i].to!=fa){
21 if (!vis[edge[i].to])dfs(edge[i].to,k);
22 else{
23 tot++;
24 if (!x)x=edge[i].to;
25 else y=edge[i].to;
26 }
27 }
28 }
29 void dfs(int k){
30 if (sz[k])return;
31 sz[k]=1;
32 for(int i=0;iv[i])g[p[v[i]]].push_back(v[i]);
44 for(int i=0;i2){
67 printf("0");
68 return 0;
69 }
70 for(int j=y;j!=i;j=f[j])p[f[j]]=j;
71 p[y]=x;
72 int s=calc();
73 for(int j=y;j!=x;j=f[j])p[j]=f[j];
74 p[x]=y;
75 ans=1LL*ans*(s+calc())%mod;
76 }
77 printf("%d",ans);
78 }