Submission #41888162

---

Source Code Expand

#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 2e5 + 10, MOD = 1e9 + 7;
int n, fa[N], sz[N], cnt[N], ff[N], mat[N], ss[N], ans, fac[N], inv[N], dep[N];
bool iscir[N], ok[N];
vector <int> edge[N], cir, edge2[N], p[N];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void dfs1(int x, int fa) {
	ff[x] = fa;
	// cout << x << " " << dep[x] << " " << fa << " " << dep[fa] << endl;
	dep[x] = dep[fa] + 1;
	// cout << x << " " << dep[x] << " " << fa << " " << dep[fa] << endl;
	for (int i: edge[x])
		if (i != fa) {
			// cout << x << " " << fa << " " << i << " " << dep[x] << " " << dep[i] << endl;
			if (!dep[i]) dfs1(i, x);
			else if (dep[i] < dep[x]) {
				while (dep[x] >= dep[i]) {
					// cout << " -> " << x << endl;
					iscir[x] = true, cir.push_back(x);
					x = ff[x];
					// return;
				} return;
			}
		}
}
void dfs2(int x, int fa) {
	// cout << "!\n";
	// for (int i: cir) cout << i << " "; cout << endl;
	// cout << x << endl;
	for (int i: edge[x])
		if (i != fa && !iscir[i]) {
			mat[i] = x;
			// cout << "! " << i << " " << x << endl;
			dfs2(i, x);
		}
}
void dfs3(int x) {
	ss[x] = 1;
	for (int i: edge2[x]) dfs3(i), ss[x] += ss[i];
	ans = (ll) ans * inv[ss[x]] % MOD;
	// cout << x << " " << ss[x] << endl;
}
int calc(int id) {
	// cout << ": " << cir.size() << endl;
	for (int i: p[id]) ok[i] = true;
	for (int i: p[id]) {
		edge2[i].clear();
		// cout << " -> " << i << " " << mat[i] << endl;
		for (int j: edge[i])
			if (j < mat[i]) edge2[i].push_back(j), ok[j] = false;
	}
	ans = 1;
	for (int i: p[id]) if (ok[i]) dfs3(i);
	return ans;
}
void init(int x) {
	fac[0] = inv[1] = 1;
	F(i, 2, x) inv[i] = (ll) (MOD - MOD / i) * inv[MOD % i] % MOD;
	F(i, 1, x) fac[i] = (ll) fac[i - 1] * i % MOD;
}
signed main() {
	read(n);
	init(2 * n);
	F(i, 1, 2 * n) fa[i] = i, sz[i] = 1;
	F(i, 1, 2 * n) {
		int x, y; read(x), read(y);
		// cout << x << " " << y + n << endl;
		edge[x].push_back(y + n);
		edge[y + n].push_back(x);
		int kx = find(x), ky = find(y + n);
		if (kx != ky) {
			fa[ky] = kx;
			sz[kx] += sz[ky];
			cnt[kx] += cnt[ky];
		} cnt[kx]++;
	}
	F(i, 1, 2 * n) {
		p[find(i)].push_back(i);
		if (fa[i] == i) {
			// cout << i << " " << sz[i] << " " << cnt[i] << endl;
			if (cnt[i] != sz[i]) return puts("0"), 0;
		}
	} int res = 1;
	// puts("!!!");
	F(i, 1, 2 * n)
		if (fa[i] == i) {
			cir.clear(); dfs1(i, 0);
			// cout << i << " " << cir.size() << endl;
			for (int j: cir) dfs2(j, 0);
			F(j, 0, SZ(cir)) mat[cir[j]] = cir[(j + 1) % cir.size()];
			// F(j, 1, 2 * n) cout << mat[j] << endl;
			int ans = calc(i);
			F(j, 0, SZ(cir)) mat[cir[j]] = cir[(j - 1 + cir.size()) % cir.size()];
			// cout << i << " " << ans << " " << calc(i) << endl;
			res = (ll) res * (ans + calc(i)) % MOD;
		}
	cout << (ll) fac[2 * n] * res % MOD;
	return 0;
}

Submission Info

Judge Result