Submission

Score: 0

User: koon

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

Language: cpp

Time: 1.095 second

Submitted On: 2026-04-23 20:27:04

#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<int> subtree;

int dfs(int u, int p) {
    int res = cnt[u].a;
    for (auto &v : adj[u]) {
        if (v == p) continue;
        res += dfs(v, u);
    }
    return subtree[u] = res;
}

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

    cin >> n >> m;
    cnt.resize(m, {0, 0});
    adj.resize(m);
    subtree.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);
        }
    }

    for (int i = 0; i < m; i++) {
        dfs(i, -1);
    }

    long long sum = 0;

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

            for (int j = 0; j < cnt[i].a; j++) {
                res.push_back(1);
            }

            for (auto &x : adj[i]) {
                res.push_back(subtree[x]);
            }

            int k = res.size();

            long long temp = 0;

            for (int a = 0; a < k; a++) {
                for (int b = a+1; b < k; b++) {
                    for (int c = b+1; c < k; c++) {
                        for (int d = c+1; d < k; d++) {
                            long long t = res[a];
                            t = (t * res[b]) % MOD;
                            t = (t * res[c]) % MOD;
                            t = (t * res[d]) % MOD;
                            temp = (temp + t) % MOD;
                        }
                    }
                }
            }

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

    cout << sum;
    return 0;
}