Language: C++


#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = 200005, MOD = 1000000007;
typedef long long i64;

class Edge {
public:
  int nxt, to;
} e[MAX_N << 2];

int head[MAX_N], cnt;
void addedge(int u, int v) {
  e[++cnt] = (Edge){head[u], v}, head[u] = cnt;
  e[++cnt] = (Edge){head[v], u}, head[v] = cnt;
}

int N, vis[MAX_N], num_e, num_v, st[MAX_N];
void dfs(int u, int v) {
  static int tot;
  st[++num_v] = u, vis[u] = ++tot;
  for (int i = head[u]; i; i = e[i].nxt)
    if (e[i].to != v) {
      if (!vis[e[i].to]) num_e++, dfs(e[i].to, u);
      else if (vis[e[i].to] < vis[u]) num_e++;
    }
}

i64 fac[MAX_N], ifac[MAX_N], inv[MAX_N];
i64 binom(int n, int m) {
  if (n < m) return 0;
  return fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}

bool flag;
int top, cir[MAX_N];

void find_circle(int u, int v) {
  if (flag) return;
  static int ti[MAX_N], fa[MAX_N];
  
  fa[u] = v, ti[u] = 1;
  
  for (int i = head[u]; i; i = e[i].nxt)
    if (e[i].to != v) {
      if (flag) return;
      if (!ti[e[i].to]) find_circle(e[i].to, u);
      else {
	int temp = u;
	do {
	  cir[top++] = temp;
	  temp = fa[temp];
	} while (temp != e[i].to);
	cir[top++] = e[i].to;
	flag = 1;
      }
    }
}

int on[MAX_N], target[MAX_N], in[MAX_N];

void dfs2(int u, int v) {
  for (int i = head[u]; i; i = e[i].nxt)
    if (e[i].to != v && !on[e[i].to]) {
      target[e[i].to] = u;
      dfs2(e[i].to, u);
    }
}

int sz[MAX_N];

i64 dfs3(int u, int v) {
  sz[u] = 0;
  i64 now = 1;
  for (int i = head[u]; i; i = e[i].nxt)
    if (e[i].to < target[u]) {
      i64 temp = dfs3(e[i].to, u);
      now = now * temp % MOD * binom(sz[u] + sz[e[i].to], sz[u]) % MOD;
      sz[u] += sz[e[i].to];
    }
  sz[u]++;
  // printf("%lld\n", now);
  return now;
}

i64 calc() {
  for (int i = 1; i <= num_v; ++i) in[st[i]] = 0;
  for (int i = 1; i <= num_v; ++i) {
    for (int j = head[st[i]]; j; j = e[j].nxt)
      if (e[j].to < target[st[i]]) in[e[j].to]++;
  }
  i64 res = 1;
  int size = 0;
  for (int i = 1; i <= num_v; ++i)
    if (in[st[i]] == 0) {
      res = res * dfs3(st[i], 0) % MOD * binom(sz[st[i]] + size, size) % MOD;
      size += sz[st[i]];
    }
  return res;
}

i64 work() {
  flag = 0;
  find_circle(st[1], 0);
  for (int i = 0; i < top; ++i) on[cir[i]] = 1;
  for (int i = 0; i < top; ++i)
    dfs2(cir[i], 0);
  i64 now = 0;
  for (int i = 0; i < top; ++i) target[cir[i]] = cir[(i + 1) % top];
  now = (now + calc()) % MOD;
  for (int i = 0; i < top; ++i) target[cir[i]] = cir[(i - 1 + top) % top];
  now = (now + calc()) % MOD;
  return now;
}

int main() {
  scanf("%d", &N);
  for (int i = 1, x, y; i <= N << 1; ++i) {
    scanf("%d%d", &x, &y);
    addedge(x, y + N);
  }

  fac[0] = ifac[0] = inv[1] = 1;
  for (int i = 1; i <= N << 1; ++i) fac[i] = fac[i - 1] * i % MOD;
  for (int i = 2; i <= N << 1; ++i) inv[i] = -(MOD / i) * inv[MOD % i] % MOD;
  for (int i = 1; i <= N << 1; ++i) ifac[i] = ifac[i - 1] * inv[i] % MOD;
  
  i64 result = 1;
  int size = 0;
    
  for (int i = 1; i <= N << 1; ++i) 
    if (!vis[i]) {
      num_e = 0, num_v = 0;
      dfs(i, 0);
      if (num_e != num_v) {
	puts("0");
	return 0;
      }
      result = result * work() % MOD * binom(size + num_v, num_v) % MOD;
      size += num_v;
    }

  printf("%lld\n", (result + MOD) % MOD);
  return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:119:3: error: 'scanf' was not declared in this scope
  119 |   scanf("%d", &N);
      |   ^~~~~
a.cc:138:9: error: 'puts' was not declared in this scope
  138 |         puts("0");
      |         ^~~~
a.cc:145:3: error: 'printf' was not declared in this scope
  145 |   printf("%lld\n", (result + MOD) % MOD);
      |   ^~~~~~
a.cc:4:1: note: 'printf' is defined in header '<cstdio>'; this is probably fixable by adding '#include <cstdio>'
    3 | #include <cstring>
  +++ |+#include <cstdio>
    4 | using namespace std;