Submission

Score: 0

User: koon

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

Language: cpp

Time: 1.095 second

Submitted On: 2026-04-23 20:24:53

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
int n, m;

bool c_h(int u) {
    if (u <= n) return true; //หมู่บ้าน
    return false; //ตำบล
}
struct node {
    int a, b;
    
    int sum() {
        return a + b;
    }
};
vector<node> cnt; 
vector<vector<int>> adj;

int count_path(int u, int p) {
    int temp = cnt[u].a;

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

    return temp;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    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);
        }
    }

    int 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 temp = 0;
            for (int j = 0; j < (1 << (int)res.size()); j++) {
                vector<int> pos;
                int temp2 = 1;
                for (int l = 0; l < (int)res.size(); l++) {
                    if (j & (1LL << l)) {
                        pos.emplace_back(l);
                    }
                }

                if (pos.size() != 4) continue;

                for (auto &x : pos) {
                    temp2 *= res[x];
                    temp2 %= MOD;
                }
                temp2 %= MOD;
                temp += temp2;
            }
            sum += temp;
            sum %= MOD;
        }
    }

    cout << sum;
    return 0;
}