Submission

Score: 100

User: GGEZLOLx3D

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

Language: cpp

Time: 0.066 second

Submitted On: 2026-03-26 00:20:43

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX 1e15
int mod=1e9+7;
int fac(int aaa){
    if(aaa==5){
        return 5;
    }
    else if(aaa==4){
        return 4;
    }
    else if(aaa<4){
        return 0;
    }
    return (aaa*fac(aaa-1))%mod;
}
signed main(){
    cin.tie(NULL)->sync_with_stdio(false);
    int n,m,i,j,nn,t,en,mon,k,a,b,st;
    cin >> n >> m;
    vector<int> sum(m+n+1,0),deg(m+n+1,0),arr[n+m+1],chi[n+m+1];

    for(i=0;i<n+m-1;i++){
        int x,y;
        cin >> x >> y;
        arr[x].push_back(y);
        arr[y].push_back(x);
        deg[x]++;
        deg[y]++;
    }
    queue<int> q;
    vector<bool> vi(m+n+1,false);
    for(i=1;i<=n;i++){
        vi[i]=true;
        q.push(i);
        sum[i]=1;
    }
    vector<int> can;
    for(i=n+1;i<=n+m;i++){
        if(deg[i]>=4){
            can.push_back(i);
        }
    }
    if(can.size()==0 || n<4){
        cout << 0;
        return 0;
    }
    /*if(m==1){
        cout << fac(n);
        return 0;
    }*/

    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int y:arr[x]){
            if(vi[y])continue;
            chi[y].push_back(x);
            deg[y]--;
            sum[y]+=sum[x];
            if(deg[y]==1){
                q.push(y);
                vi[y]=true;
            }
        }

    }
    int ans=0;
    for(i=0;i<can.size();i++){
        vector<int> all;
        for(int x:chi[can[i]]){
            all.push_back(sum[x]);

        }
        all.push_back(n-sum[can[i]]);
        int pb=0;
        int si=all.size();
        vector<vector<int>> dp(si+1,vector<int>(5,0));
        dp[0][0]=1;
        for(j=1;j<all.size()+1;j++){
            dp[j][0]=1;
            for(k=1;k<5;k++){
                dp[j][k]=((dp[j-1][k-1]*all[j-1])%mod+dp[j-1][k])%mod;
            }
        }
        /*for(j=0;j<=si;j++){
            for(k=0;k<5;k++){
                cout << dp[j][k] << " ";
            }cout << "\n";
        }//*/
        ans=(ans+dp[si][4])%mod;
    }
    /*for(i=1;i<=n+m;i++){
        cout << sum[i] << " ";
    }//*/
    cout << ans;
}
/*
5 18 30
1 2 93 84 2
12 1261 0
LRRRRRRRRRRR

9 12 9
LURURDRUU

7 -4 3
RULUULD

7 2 7 4 9 3 3 5 8
5 2
0 1
2 2
3 6
6 6
9 10
10
15

5 2
0 0
2 0
7 0
4 0
10 0
10
3
*/