Submission

Score: 27

User: qweqwe

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

Language: cpp

Time: 1.096 second

Submitted On: 2026-03-25 22:45:33

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define qweqwe cin.tie(0)->sync_with_stdio(0)
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using db = long double;

vector<vector<int>> graph(100001);
unordered_set<int> spe; // SPE-CHANNNNN!!!!
vector<int> dp(100001);
const ll MOD = 1e9+7;

int dfs(int x,int p){
	if (!spe.count(x)) dp[x]=graph[x].size();
	
	for (int i:graph[x]){
		if (i==p) continue;
		dp[x] += dfs(i,x);
	}
	
	return dp[x];
}

int main(){
	qweqwe;
	int n,m;cin >> n >> m;
	graph.resize(n+m+1);
	dp.resize(n+m+1);
	for (int i=0;i<n;i++){
		int st,en;
		cin >> st >> en;
		graph[st].push_back(en);
		graph[en].push_back(st);
	}
	for (int i=0;i<m-1;i++){
		int st,en;
		cin >> st >> en;
		graph[st].push_back(en);
		graph[en].push_back(st);
	}
	
	for (int i=n+1;i<=n+m;i++){
		spe.insert(i);
	}
	/*
	for (int i=1;i<=n+m;i++){
		cout << dp[i] << " ";
	}cout << "\n";
	*/
	int realsum=0;
	for (int i=n+1;i<=n+m;i++){
		int s = graph[i].size();
		if (s<4) continue;
		
		fill(dp.begin(),dp.end(),0);
		dfs(i,-1);
		vector<int> pf(s+1,0);
		
		for (int a=s;a>=3;a--){
			pf[a-1]=pf[a];
			for (int b=a+1;b<=s;b++){
				//cout << a << " " << b << '\n';
				pf[a-1]+=(dp[graph[i][a-1]]*dp[graph[i][b-1]])%MOD;
				pf[a-1]%=MOD;
			}
			/*
			for (int j=2;j<=s;j++){
				cout << pf[j] << " ";
			}cout << '\n';
			*/
		}
		
		for (int a=1;a<=s-2;a++){
			for (int b=a+1;b<=s-2;b++){
				//ll gap = s-b-1;
				//ll sum = (gap*gap+gap)/2;
				
				//cout << a << " " << b << "\n";
				
				ll mul = (dp[graph[i][a-1]]*dp[graph[i][b-1]])%MOD;
				
				//cout << mul << " " << (mul%MOD*pf[b]%MOD)%MOD << "\n";
				
				realsum += (mul%MOD*pf[b]%MOD)%MOD;
				realsum%=MOD;
			}
		}//cout << realsum << "\n";
	}
	cout << realsum;
	return 0;
}