Submission

Score: 7

User: GGEZLOLx3D

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

Language: cpp

Time: 1.094 second

Submitted On: 2026-03-25 23:36:46

#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 jj,jjj,jjjj;
        int pb=0;
        for(j=0;j<all.size()-3;j++){
            for(jj=j+1;jj<all.size()-2;jj++){
                for(jjj=jj+1;jjj<all.size()-1;jjj++){
                    for(jjjj=jjj+1;jjjj<all.size();jjjj++){
                        pb=(pb+(((((all[j]*all[jj])%mod)*all[jjj])%mod)*all[jjjj])%mod)%mod;
                    }
                }
            }
        }
        //cout << pb << "\n";
        ans=(ans+pb)%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
*/