题解

#include<bits/stdc++.h>
#define mo 1000000007
#define ll long long 
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

struct node {
	int to, nxt;
}e[800001];
int k, n[50001], m[50001], count[500001], mxn[50001];
int le[200001], KK, x, y, dis[200001], cnt[500001];
int nmb[200001];
vector <ll> minn[50001][2];
vector <pair<int, int> > tong[400001];
bool in[200001];
ll ans;

struct abab {
	int x;
};
bool operator <(abab x, abab y) {
	return mxn[x.x] > mxn[y.x];
}
priority_queue <abab> mg;

void add(int x, int y) {
	e[++KK] = (node){y, le[x]}; le[x] = KK;
	e[++KK] = (node){x, le[y]}; le[y] = KK;
}

struct ztzt {
	int dis, now;
};
bool operator <(ztzt x, ztzt y) {
	return x.dis > y.dis;
}
priority_queue <ztzt> q;

void dij(int x) {
	while (!q.empty()) q.pop();
	dis[0] = INF;
	for (int i = 1; i <= n[x]; i++) {
		dis[i] = dis[i + n[x]] = INF;
		in[i] = in[i + n[x]] = 0;
	}
	dis[1] = 0; q.push((ztzt){0, 1});
	while (!q.empty()) {
		int now = q.top().now;
		q.pop();
		if (in[now]) continue;
		in[now] = 1;
		for (int i = le[now]; i; i = e[i].nxt)
			if (!in[e[i].to] && dis[e[i].to] > dis[now] + 1) {
				dis[e[i].to] = dis[now] + 1;
				q.push((ztzt){dis[e[i].to], e[i].to});
			}
	}
}

struct XDtree {
	ll val[500001 << 2];
	
	void clean() {
		memset(val, 0, sizeof(val));
	}
	
	void up(int now) {
		val[now] = val[now << 1] * val[now << 1 | 1] % mo;
	} 
	
	void insert(int now, int l, int r, int pl, int va) {
		if (l == r) {
			val[now] = (val[now] + va + mo) % mo;
			return ;
		}
		
		int mid = (l + r) >> 1;
		if (pl <= mid) insert(now << 1, l, mid, pl, va);
			else insert(now << 1 | 1, mid + 1, r, pl, va);
		
		up(now); 
	}
	
	ll query(int now, int l, int r, int L, int R) {
		if (L > R) return 1;
		if (L <= l && r <= R) {
			return val[now];
		}
		
		int mid = (l + r) >> 1;
		ll re = 1;
		if (L <= mid) re = (re * query(now << 1, l, mid, L, R)) % mo;
		if (mid < R) re = (re * query(now << 1 | 1, mid + 1, r, L, R)) % mo;
		return re;
	}
}T;

ll get_max(int op) {
	ans = 0; int maxn = -1;
	for (int i = 1; i <= k; i++)
		for (int j = 0; j < n[i]; j++) {
			int vl = -1;
			if (op == 1) vl = minn[i][0][j];
				else if (op == 2) vl = minn[i][1][j];
					else {
						vl = max(minn[i][0][j], minn[i][1][j]);
					}
			if (vl == dis[0]) continue;
			nmb[i]++;
			tong[vl].push_back(make_pair(i, j));
			maxn = max(maxn, vl);
		}
	
	for (int i = 1; i <= k; i++) {
		T.insert(1, 1, k, i, nmb[i]);
	}
	for (int i = maxn; i >= 1; i--) {
		for (int j = 0; j < tong[i].size(); j++) {
			ans = (ans + i * (T.query(1, 1, k, 1, tong[i][j].first - 1) * T.query(1, 1, k, tong[i][j].first + 1, k) % mo) % mo) % mo;//剩余部分的乘积
			T.insert(1, 1, k, tong[i][j].first, -1);//减少
		}
	}
	
	for (int i = 1; i <= maxn; i++)
		tong[i].clear();
	T.clean();
	memset(nmb, 0, sizeof(nmb));
	return ans;
}

int main() {
	cin>>k;
	for (int i = 1; i <= k; i++) {
		cin>>n[i]>>m[i];
		
		KK = 0; for (int j = 1; j <= 2 * n[i]; j++) le[j] = 0;
		for (int j = 1; j <= m[i]; j++) {
			cin>>x>>y;
			add(x, y + n[i]); add(x + n[i], y);
		}
		
		dij(i);
		for (int j = 1; j <= n[i]; j++)
			minn[i][0].push_back(dis[j]), minn[i][1].push_back(dis[j + n[i]]);
	}
	
	cout<<(get_max(1) + get_max(2) - get_max(3) + mo) % mo;
	
	return 0;
}