times.cpp

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define fr first
#define se second

int n, M = 1e9 + 7, ways = 1;
vector<pii> adj;
vector<int> color;

void dfs(int node) {
    if (color[adj[node].fr] && (color[adj[node].fr] == color[node])) {
        ways = 0;
    } else if (!color[adj[node].fr]) {
        color[adj[node].fr] = 3 - color[node];
        dfs(adj[node].fr);
    }
    if (color[adj[node].se] && (color[adj[node].se] == color[node])) {
        ways = 0;
    } else if (!color[adj[node].se]) {
        color[adj[node].se] = 3 - color[node];
        dfs(adj[node].se);
    }
}

int32_t main() {
    cin >> n;
    adj.resize(n + 1);
    color.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> adj[i].fr >> adj[i].se;
    }
    for (int i = 1; i <= n; i++) {
        if (!color[i]) {
            ways = (ways + ways) % M;
            color[i] = 1;
            dfs(i);
            if (!ways) break;
        }
    }
    cout << ways << "\n";
}