Language: C++

#include <iostream>
#include <vector>
#include <tuple>

#define rep(i,i0,n) for (int (i) = (i0); (i) < (n); ++(i))

using namespace std;

class UnionFind {
public:
    UnionFind(int);
    int find(int);
    void unite(int, int);
private:
    vector<int> table;
};

UnionFind::UnionFind(int size) {
    table.resize(size);
    fill(table.begin(), table.end(), -1);
}

int UnionFind::find(int x) {
    while (0 <= table[x])
        x = table[x];
    return x;
}

void UnionFind::unite(int x, int y) {
    int rx = find(x);
    int ry = find(y);
    if (rx != ry) {
        int dx = -table[rx];
        int dy = -table[ry];
        if (dx != dy) {
            if (dx < dy) {
                table[rx] = ry;
            } else {
                table[ry] = rx;
            }
        } else {
            table[rx] -= 1;
            table[ry] = rx;
        }
    }
}


const long M = 1e9 + 7;
int N;
long F[202020];
int groups[202020];
int pair_table[202020];
int counts[202020];
long perms[202020];
vector< vector<int> > edges;
vector<bool> is_root;


long powmod(long a, long x, long m) {
    long r = 1;
    while (0 < x) {
        if (x & 1) {
            r *= a;
            r %= m;
        }
        x >>= 1;
        a *= a;
        a %= m;
    }
    return r;
}


void calc_node(int node, const vector< vector<int> > &tree) {
    if (tree[node].size() == 0) {
        counts[node] = 1;
        perms[node] = 1;
    } else {
        int c;
        
        c = 0;
        for (int child : tree[node]) {
            calc_node(child, tree);
            c += counts[child];
        }
        counts[node] = c + 1;

        long p;

        p = F[c];
        for (int child : tree[node]) {
            p *= powmod(F[counts[child]], M - 2, M);
            p %= M;
            p *= perms[child];
            p %= M;
        }
        perms[node] = p;
    }
}

long calc(const vector<int> &nodes) {
    vector< vector<int> > tree;
    int nv, nnv;
    int c;
    long p;

    fill(is_root.begin(), is_root.end(), true);
    tree.resize(2 * N);

    for (int v : nodes) {
        nv = pair_table[v];
        nnv = pair_table[nv];
        if (v < nnv) {
            is_root[v] = false;
            tree[nv].push_back(v);
        }
    }

    c = 0;
    for (int v : nodes) {
        if (is_root[v]) {
            calc_node(v, tree);
            c += counts[v];
        }
    }

    p = F[c];
    for (int v : nodes) {
        if (is_root[v]) {
            p *= powmod(F[counts[v]], M - 2, M);
            p %= M;
            p *= perms[v];
            p %= M;
        }
    }

    return p;
}



long solve(const vector<int> &nodes) {
    int pv, nv;

    for (int v : nodes) {
        if (edges[v].size() == 1) {
            nv = edges[v].back();
            edges[v].pop_back();
            pair_table[v] = nv;
            edges[nv].erase(find(edges[nv].begin(), edges[nv].end(), v));
            pv = v; v = nv;
            while (edges[v].size() == 1) {
                nv = edges[v].back();
                edges[v].pop_back();
                pair_table[v] = nv;
                edges[nv].erase(find(edges[nv].begin(), edges[nv].end(), v));
                pv = v; v = nv;
            }
        }
    }

    int v0 = 0;
    int v1, v2;
    for (int v : nodes) {
        if (edges[v].size() != 0) {
            v0 = v;
            break;
        }
    }
    v1 = edges[v0][0];
    v2 = edges[v0][1];

    long r = 0;
    int v;
    int nv0, nv1, nv2;
    rep(d, 0, 2) {
        nv0 = (d == 0) ? v1 : v2;
        nv = nv0; v = v0;
        pair_table[v] = nv;
        pv = v; v = nv;
        while (v != v0) {
            nv1 = edges[v][0];
            nv2 = edges[v][1];
            nv = (nv1 != pv) ? nv1 : nv2;
            pair_table[v] = nv;
            pv = v; v = nv;
        }
        r += calc(nodes);
        r %= M;
    }

    return r;
}


int main(int argc, const char * argv[]) {
    vector< tuple<int, int> > balls;
    int x, y;

    cin >> N;
    rep(i, 0, 2 * N) {
        cin >> x >> y;
        balls.push_back(make_tuple(x - 1, N + y - 1));
    }

    {
        long p = 1;
        rep(i, 1, 2 * N + 1) {
            p *= i;
            p %= M;
            F[i] = p;
        }
    }

    UnionFind uf(2 * N);
    edges.resize(2 * N);
    is_root.resize(2 * N);

    for (tuple<int, int> t : balls) {
        int x = get<0>(t);
        int y = get<1>(t);
        uf.unite(x, y);
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    long ans = F[2 * N];
    vector<int> nodes;
    unsigned long num_nodes, num_edges;

    
    rep(i, 0, 2 * N) {
        if (edges[i].empty()) {
            cout << 0 << endl;
            return 0;
        }
    }

    rep(i, 0, 2 * N) groups[i] = uf.find(i);
    
    rep(i, 0, 2 * N) {
        if (groups[i] == i) {
            nodes.clear();
            rep(v, 0, 2 * N) {
                if (groups[v] == i) {
                    nodes.push_back(v);
                }
            }
            num_nodes = nodes.size();
            num_edges = 0;
            for (int v : nodes) {
                num_edges += edges[v].size();
            }
            num_edges /= 2;
            if (num_nodes != num_edges) {
                cout << 0 << endl;
                return 0;
            }
            ans *= powmod(F[num_nodes], M - 2, M);
            ans %= M;
            ans *= solve(nodes);
            ans %= M;
        }
    }

    cout << ans << endl;
    return 0;
}


Compiler output:
a.cc: In function 'long int solve(const std::vector<int>&)':
a.cc:151:33: error: no matching function for call to 'find(std::vector<int>::iterator, std::vector<int>::iterator, int&)'
  151 |             edges[nv].erase(find(edges[nv].begin(), edges[nv].end(), v));
      |                             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/locale_facets.h:48,
                 from /usr/include/c++/14/bits/basic_ios.h:37,
                 from /usr/include/c++/14/ios:46,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:151:33: note:   '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' is not derived from 'std::istreambuf_iterator<_CharT>'
  151 |             edges[nv].erase(find(edges[nv].begin(), edges[nv].end(), v));
      |                             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:157:37: error: no matching function for call to 'find(std::vector<int>::iterator, std::vector<int>::iterator, int&)'
  157 |                 edges[nv].erase(find(edges[nv].begin(), edges[nv].end(), v));
      |                                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/14/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
a.cc:157:37: note:   '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' is not derived from 'std::istreambuf_iterator<_CharT>'
  157 |                 edges[nv].erase(find(edges[nv].begin(), edges[nv].end(), v));
      |                                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~