Submission

Score: 45

User: koon

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

Language: cpp

Time: 1.094 second

Submitted On: 2026-04-24 13:28:29

#ifdef _WIN32
    #define getchar_unlocked _getchar_nolock
#endif
#include <iostream>
#include <vector>
#include <cstdint>
#include <cmath>
#include <algorithm>
using namespace std;
#define int long long
const int MOD = 1e9+7;

inline int readint() {
    int x = 0, c = getchar_unlocked();

    while (c < '0' || c > '9') c = getchar_unlocked();

    while (c >= '0' && c <= '9') {
        x = x*10 + (c - '0');
        c = getchar_unlocked();
    }

    return x;
}

struct node {
    int a, b;
    vector<int> adj;

    int sum() {
        return a + b;
    }
};

int n, m;
// vector<int> dp1;
// vector<vector<int>> adj;
vector<node> vec;

inline bool c_h(const int &u) {
    return u > n;
}

int dfs(int u, int p) { 
    int sum = vec[u].a;

    for (auto &x : vec[u].adj) {
        if (x == p) continue;
        sum += dfs(x, u);
    }

    return sum;
}

int32_t main() {
    cin >> n >> m;
    // adj.resize(n+m+1);
    // dp1.resize(n+m+1, -1);
    // node temp;
    // temp.a = 0LL;
    // temp.b = 0LL;
    vec.resize(n+m+1, {0, 0, {}});
    for (int i = 0; i < n+m-1; i++) {
        int u, v; 
        cin >> u >> v;
        if (c_h(u)) {
            if (c_h(v)) {
                vec[u].b++;
            } else {
                vec[u].a++;
            }
        }
        if (c_h(v)) {
            if (c_h(u)) {
                vec[v].b++;
            } else {
                vec[v].a++;
            }
        }
        vec[u].adj.push_back(v);
        vec[v].adj.push_back(u);
    }

    int sum = 0;

    for (int i = n+1; i <= m+n; i++) {
        // cout << vec[i].sum() << ' ';
        if (vec[i].sum() >= 4) {
            vector<int> res(vec[i].a, 1);

            for (auto &u : vec[i].adj) {
                if (!c_h(u)) continue;
                res.push_back(dfs(u, i));
            }

            int s1 = 0, s2 = 0, s3 = 0, s4 = 0;

            for (auto i : res) {
                s4 += s3*i;
                s4 %= MOD;
                s3 += s2*i;
                s3 %= MOD;
                s2 += s1*i;
                s2 %= MOD;
                s1 += i;
                s1 %= MOD;
            }
            sum += s4;
            sum %= MOD;
        }
    }

    cout << sum;
    return 0;
}