Submission

Score: 0

User: GGEZLOLx3D

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

Language: cpp

Time: 1.093 second

Submitted On: 2026-03-25 22:03:23

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX 1e15
signed main(){
    cin.tie(NULL)->sync_with_stdio(false);
    int n,m,i,j,nn,t,en,mon,k,a,b,st,mod=1e9+7;
    cin >> n >> m;
    vector<int> sum(m+n+1,0),deg(m+n+1,0),arr[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);
        }
    }
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int y:arr[x]){
            if(vi[y])continue;
            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:arr[can[i]]){
            all.push_back(sum[x]);

        }
        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
*/