Submission

Score: 7

User: koon

Problemset: อพยพปลอดภัย (Quartet)

Language: cpp

Time: 1.092 second

Submitted On: 2026-04-23 20:39:09

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9+7;
int n, m;

bool c_h(int u) {
    return u <= n;
}

struct node {
    int a, b;
    int sum() { return a + b; }
};

vector<node> cnt;
vector<vector<int>> adj;
vector<vector<int>> memo;

int count_path(int u, int p) {
    int &ret = memo[u][p];
    if (ret != -1) return ret;

    long long temp = cnt[u].a;

    for (auto &x : adj[u]) {
        if (x == p) continue;
        temp += count_path(x, u);
        if (temp >= MOD) temp %= MOD;
    }

    return ret = temp % MOD;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m;

    cnt.resize(m, {0, 0});
    adj.resize(m);
    memo.assign(m, vector<int>(m, -1));

    for (int i = 0; i < n + m - 1; i++) {
        int a, b;
        cin >> a >> b;

        if (!c_h(a) && c_h(b)) cnt[a-n-1].a++;
        else if (!c_h(b) && c_h(a)) cnt[b-n-1].a++;
        else {
            cnt[a-n-1].b++;
            cnt[b-n-1].b++;
            adj[a-n-1].push_back(b-n-1);
            adj[b-n-1].push_back(a-n-1);
        }
    }

    long long sum = 0;

    for (int i = 0; i < m; i++) {
        if (cnt[i].sum() >= 4) {
            vector<int> res;

            for (int j = 0; j < cnt[i].a; j++) res.push_back(1);
            for (auto &x : adj[i]) res.push_back(count_path(x, i));

            int sz = res.size();
            long long temp = 0;

            for (int j = 0; j < (1 << sz); j++) {
                int bits = __builtin_popcount(j);
                if (bits != 4) continue;

                long long temp2 = 1;

                for (int l = 0; l < sz; l++) {
                    if (j & (1 << l)) {
                        temp2 = (temp2 * res[l]) % MOD;
                    }
                }

                temp = (temp + temp2) % MOD;
            }

            sum = (sum + temp) % MOD;
        }
    }

    cout << sum;
    return 0;
}