Codeforces859E Desk Disorder

考虑一种比较特殊的连边方式：每个原来的座位连向新的座位。

可以发现不同连通块之间没有影响，所以分别计算答案。对于一个连通块，因为图中所有点的出度小于等于 $1$ 的缘故，只有可能是一棵树或者一棵基环树。对于树的情况，只有树的大小种可能（枚举哪个点没有被坐）。对于基环树的情况，将环与树剖分开来看，树只有一种可能，而环只有两种可能，所以基环树的情况的总方案数是 $2$。

并查集维护即可。

#include <iostream>
#include <cstdio>
const int MAXN = 1e5;
const int MOD = 1e9 + 7;
int n, ans;
int father[MAXN << 1 | 1], size[MAXN << 1 | 1];
bool vis[MAXN << 1 | 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
int find(int x) {
  return father[x] == x ? x : father[x] = find(father[x]);
}
int main() {
  n = read();
  for (int i = 1; i <= 2 * n; ++i) father[i] = i, size[i] = 1;
  ans = 1;
  for (int i = 1; i <= n; ++i) {
    int u = read(), v = read();
    vis[u] = 1;
    if (u == v) continue;
    int U = find(u), V = find(v);
    if (U == V) {
      ans = 1LL * ans * 2 % MOD;
    }
    size[V] += size[U];
    father[U] = V;
  }
  for (int i = 1; i <= 2 * n; ++i) {
    if (!vis[i]) ans = 1LL * ans * size[i] % MOD;
  }
  printf("%d\n", ans);
  return 0;
}