Dựng một đồ thị ~2~ phía, ~2 \times 10^5~ đỉnh bên trái sẽ tương ứng cho các hàng, tương tự, ~2 \times 10^5~ đỉnh bên phải sẽ tương ứng cho các cột. ~2~ đỉnh bất kì ở ~2~ phía sẽ có cạnh nối khi và chỉ khi có một quân xe ở vị trí tương ứng.

Nhận xét: nếu đồ thị tạo ra được chu trình, thì tập hợp các quân xe trong chu trình đó sẽ phải cùng ở lại hoặc cùng bị gỡ bỏ. Còn nếu không phải là chu trình, các quân xe đó sẽ bị loại bỏ vì đỉnh nối các quân xe đó sẽ có bậc là ~1~ đồng nghĩa với việc hàng/cột đó sẽ bị thống trị.

Vì bậc của mỗi đỉnh trong đồ thị không quá ~2~ nên ta sử dụng ~DFS~ để đếm số chu trình trong ~O(N)~

Đáp án bài toán sẽ là: ~2^k~ với ~k~ là số chu trình.

Độ phức tạp: ~O(N)~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef unsigned long long ull; 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAX = 5e5+5;
const int LOG = 20;
const ll MOD = 1e9+7;
const ll INF = 1e15+5;
const int SQRT = 44721;

ll add(ll a, ll b) { return (a+b) % MOD; }
ll sub(ll a, ll b) { return (a-b+MOD) % MOD; }
ll mul(ll a, ll b) { return (a*b) % MOD; }

int n;
bool visited[MAX];
vector<int> adj[MAX];

int pw(int val, int temp) {
    int curr = 1;

    while(temp > 0) {
        if(temp & 1) curr = mul(curr, val);
        val = mul(val, val);
        temp >>= 1;
    }

    return curr;
}

void dfs(int v) {
    visited[v] = 1;
    foa(u, adj[v]) {
        if(!visited[u]) dfs(u);
    }
}

int solve() {
    fo(i, 1, MAX-1) {
        if(!visited[i] && sz(adj[i]) == 1) dfs(i); 
    }
    int cyc = 0;
    fo(i, 1, MAX-1) {
        if(!visited[i] && sz(adj[i]) == 2) {
            cyc++;
            dfs(i);   
        } 
    }
    return pw(2, cyc);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    cin >> n;
    fo(i, 1, n) {
        int r, c;
        cin >> r >> c;
        c += 2e5;
        adj[r].pb(c);
        adj[c].pb(r);
    }
    cout << solve();
}