Submission

Score: 45

User: nozmid

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

Language: cpp

Time: 0.040 second

Submitted On: 2026-04-23 22:35:26

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define emb emplace_back

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

int n, m;
vector<int> adj[maxn];
int dp[maxn];
ll sum[5], res;

int dfs(int u, int pa){
	if(u <= n) dp[u] = 1;
	for(auto v : adj[u]){
		if(v == pa) continue;
		dp[u] += dfs(v, u);
	}
	return dp[u];
}

void dfs2(int u, int pa){
	int tmpp = dp[pa], tmpu = dp[u];
	if(pa != -1){
		dp[pa] -= tmpu;
		dp[u] = tmpp;
	}
	//memset(sum, 0, sizeof(sum));
	for(int i=0;i<=4;++i) sum[i] = 0;
	sum[0] = 1;
	for(auto v : adj[u]){
		for(int i=4;i>=1;--i){
			sum[i] = (sum[i] + (sum[i-1]*dp[v]) % mod) % mod;
		}
	}
	res = (res + sum[4]) % mod;
	for(auto v : adj[u]){
		if(v == pa) continue;
		dfs2(v, u);
	}
	if(pa != -1){
		dp[pa] = tmpp;
		dp[u] = tmpu;
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i=0;i<n+m-1;++i){
		int u, v;
		cin >> u >> v;
		adj[u].emb(v);
		adj[v].emb(u);
	}
	dfs(n+1, -1);
	dfs2(n+1, -1);
	cout << res;
}