Submission

Score: 7

User: koon

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

Language: cpp

Time: 1.094 second

Submitted On: 2026-04-23 20:45:26

#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;
int count_path(int u, int p) {
    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 temp % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    cnt.resize(m, {0, 0});
    adj.resize(m);

    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 mask = 0; mask < (1 << sz); mask++) {
                if (__builtin_popcount(mask) != 4) continue;

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

                temp = (temp + prod) % MOD;
            }

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

    cout << sum << '\n';
    return 0;
}