考虑一个构造，对于坐标$(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<bits/stdc++.h>
2 using namespace std;
3 #define N 200005
4 #define mod 1000000007
5 struct ji{
6 int nex,to;
7 }edge[N<<1];
8 vector<int>v,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;i<g[k].size();i++){
33 dfs(g[k][i]);
34 sz[k]+=sz[g[k][i]];
35 }
36 }
37 int calc(){
38 for(int i=0;i<v.size();i++){
39 sz[v[i]]=0;
40 g[v[i]].clear();
41 }
42 for(int i=0;i<v.size();i++)
43 if (p[p[v[i]]]>v[i])g[p[v[i]]].push_back(v[i]);
44 for(int i=0;i<v.size();i++)dfs(v[i]);
45 int ans=1;
46 for(int i=0;i<v.size();i++)ans=1LL*ans*inv[sz[v[i]]]%mod;
47 return ans;
48 }
49 int main(){
50 fac[0]=inv[0]=inv[1]=1;
51 for(int i=1;i<N-4;i++)fac[i]=1LL*fac[i-1]*i%mod;
52 for(int i=2;i<N-4;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
53 scanf("%d",&n);
54 memset(head,-1,sizeof(head));
55 for(int i=1;i<=2*n;i++){
56 scanf("%d%d",&x,&y);
57 add(x,y+n);
58 add(y+n,x);
59 }
60 ans=fac[2*n];
61 for(int i=1;i<=2*n;i++)
62 if (!vis[i]){
63 v.clear();
64 x=y=tot=0;
65 dfs(i,0);
66 if (tot>2){
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 }
