这蓝题有点困难。

考虑从 $(1,1,1,\dots,1)$ 走到 $(p_1,p_2,\dots,p_n)$。有些维度可能先到，那么它可以在某条边上来回跳，即在一张图上，如果 $n$ 条边可达，那么 $n+2$ 条边也可达。

那么一个点需要分别处理一下到这个点的走奇/偶条边的最短路。边权都是 $1$，BFS 即可。第 $k$ 张图第 $x$ 个点的走奇数条边的最短路记为 $o_{x,k}$，偶数记为 $e_{x,k}$。

从 $(1,1,1,\dots,1)$ 走到 $(p_1,p_2,\dots,p_n)$ 的最短路可以表示为这个：

$$\min\{\max\{o_{p_i,i}\},\max\{e_{p_i,i}\}\} \\ =\max\{o_{p_i,i}\} + \max\{e_{p_i,i}\}-\max\{\max\{o_{p_i,i}\},\max\{e_{p_i,i}\}\}\\ = \max\{o_{p_i,i}\} + \max\{e_{p_i,i}\} - \max\{\max\{o_{p_i,i},e_{p_i,i}\}\}\\$$

现在变成三个只和点权的 $\max$ 有关的东西了。而对于这种，只需要按照点权排序，加入第 $i$ 个点时的答案就是其余的图已经加入的点的数量的乘积。这个维护起来显然是简单的。三次点权分别是 $o,e,\max\{o,e\}$。

复杂度可以线性，只是我逆元懒得线性处理。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll mod=1e9+7,inf=1e18;
ll k,v,uu,vv,prod,ans,cntpos,lstcnt,n[50005],m[50005];
ll inv[200005];
ll cnt[50005],dis[200005][2];
ll w[200005],gr[200005];
ll p[200005];
vector<ll> son[200005];
bool vis[200005][2];
bool cmp(ll x,ll y){return w[x]<w[y];}
ll qpow(ll x,ll y){ll res=1;while(y){if(y&1)res=res*x%mod;y>>=1;x=x*x%mod;}return res;}
void dij(ll x)
{
	for(int i=x;i<=v;i++) dis[i][0]=inf,dis[i][1]=inf;
	dis[x][0]=0;
	queue<pii> q;
	q.push({x,0});
	vis[x][0]=true;
	while(!q.empty())
	{
		pii nd=q.front();
		q.pop();
		for(int i=0;i<son[nd.first].size();i++)
			if(!vis[son[nd.first][i]][nd.second^1])
			{
				dis[son[nd.first][i]][nd.second^1]=dis[nd.first][nd.second]+1; 
				vis[son[nd.first][i]][nd.second^1]=true;
				q.push({son[nd.first][i],(nd.second^1)});
			}
	}
}
ll cac()
{
	ll res=0;
	prod=0,cntpos=0,lstcnt=0;
	for(int i=1;i<=k;i++) cnt[i]=0;
	for(int i=1;i<=v;i++) p[i]=i;
	sort(p+1,p+v+1,cmp);
	for(int i=1;i<=v;i++)
	{
		lstcnt=cntpos;
		ll tt=prod*inv[cnt[gr[p[i]]]]%mod;
		if(!cnt[gr[p[i]]]) cntpos++;
		cnt[gr[p[i]]]++;
		if(cntpos==k&&lstcnt<k)
		{
			prod=1;
			for(int j=1;j<=k;j++) prod=prod*cnt[j]%mod;
			tt=prod;
		}
		if(w[p[i]]<inf) res=(res+w[p[i]]*tt)%mod;
		prod=prod*inv[cnt[gr[p[i]]]-1]%mod*cnt[gr[p[i]]]%mod;
	}
	return res;
}
int main()
{
	inv[0]=1; 
	for(int i=1;i<=200000;i++) inv[i]=qpow(i,mod-2);
	scanf("%lld",&k);
	for(int i=1;i<=k;i++)
	{
		scanf("%lld%lld",&n[i],&m[i]);
		for(int j=v+1;j<=v+n[i];j++) gr[j]=i;
		for(int j=1;j<=m[i];j++)
		{
			scanf("%lld%lld",&uu,&vv);
			son[uu+v].push_back(vv+v);
			son[vv+v].push_back(uu+v);
		}
		v+=n[i];
		dij(v-n[i]+1);
	}
	for(int i=1;i<=v;i++) w[i]=dis[i][0];
	ans+=cac();
	for(int i=1;i<=v;i++) w[i]=dis[i][1];
	ans+=cac();
	for(int i=1;i<=v;i++) w[i]=max(dis[i][0],dis[i][1]);
	ans-=cac();
	printf("%lld\n",(ans%mod+mod)%mod);
	return 0;
}

/* (Analysis by hansang) 
Full Solution (original constraints) 
1.看过数据就应该意识到不可以直接构造出新图跑最短路 
2.仔细观察得到新图和原图的关系：
    在新图上每走一步就相当于在原图的对应图上走一步。 
    那么从(1, 1...1, 1)走到(a1, a2..., ak-1, ak)， 
    就相当于分别从各个对应的图： 1走到 a1，1走到 a2...1走到 ak-1，1走到 ak。 
    那这样只用每个原图分别跑最短路即可。 
3.但思考后可得：
	当要到达特定的一点时，只有原图的 k个最短路径，经过的边总数奇偶性相同，才能有解。
    因为图是无向图，可以来回走一条边，来达成 "等等别的图"的目的。 
4.那我们可以确定做法：
    先通过 bfs跑出各个原图的奇偶最短路。
    然后每次循环选出一个点作为从起点到该点距离最大的点：
		统计距离小于等于它的点：每个图累计ai个点，将他们相乘得sum。
		直到 k个原图都跑过，sum再乘上该点的距离就为答案。 
5.还有一个问题：奇偶性。
	我们要取奇数距离和偶数距离的最小值，可以理解为 min(max ji_i, max ou_i)
	明显不好搞，但是我们可以将上面的式子变为 max ji_i+max ou_i-max(ji, ou)
	分别求出值，组成一个容斥，即可完成本题。 
还有别的细节我写代码注释里了。。 
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10, inf=0x3f3f3f3f;
typedef long long LL;
const LL P=1e9+7;
LL inv[N]; int ji[N], ou[N], a[N];  
vector<int> G[N], v[3][N]; int n, m, T;
void bfs(int ti){
	for(int i=0; i<=n; i++) ji[i]=ou[i]=N-10; 
	//设一个最大值（判断无解用的），这里偷懒设成 N-10 
	queue<int> Q; Q.push(1); ou[1]=0; //距离为 0当然是偶数 
	while(!Q.empty()){
		int x=Q.front(); Q.pop();
		if(x>n){
			x-=n;
			for(int y: G[x]) if(ou[y]==N-10) ou[y]=ji[x]+1, Q.push(y);
			//只有还没有解的时候才更新，因为这里用的队列，不用担心当前值没有后来值优 
		}
		else
			for(int y: G[x]) if(ji[y]==N-10) ji[y]=ou[x]+1, Q.push(y+n); //+n以区别奇偶 
	}
	for(int i=1; i<=n; i++){
		v[0][ji[i]].push_back(ti);
		v[1][ou[i]].push_back(ti);
		int t=max(ji[i], ou[i]);
		v[2][t].push_back(ti);
	}
}
LL calc(vector<int> *vv){
	memset(a, 0, sizeof(a));
	int d=0; LL sum=1, res=0;
	for(int i=0; i<=N-11; i++) for(int j: vv[i]){ //i最大值不能取到前面设的最大值 
		//最难理解的地方：sum是前文提到的乘积，但这里只需要 sum乘当前 ai的最大值
		//我们无法确定 ai的值，只能边循环边乘，但前面的 sum已经乘过那个较小的 ai了，怎么办？
		//这里可以用到逆元，只要 sum乘上之前那个较小 ai的逆元再乘上当前 ai就可以了！ 
		if(a[j]) sum=sum*inv[a[j]]%P;
		//其实还有一个小细节：如果当前图编号为 x，那么 aj就不给 sum贡献，这里巧妙的达到了。 
		else d++; //统计跑过多少图 
		if(d==T) res=(res+sum*i)%P; //***全都跑过了才可以累计答案！ 
		a[j]++; sum=sum*a[j]%P; 
        //printf("%d %d %d %d\n", j, a[j], sum, res); 
	}
	return res;
}
int main(){
	inv[1]=1; for(int i=2; i<=N-10; i++) inv[i]=(P-P/i)*inv[P%i]%P; //线性求逆元 
	memset(v, 0, sizeof(v));
	scanf("%d", &T);
	for(int ti=1; ti<=T; ti++){
		scanf("%d%d", &n, &m);
		memset(G, 0, sizeof(G));
		for(int i=1; i<=m; i++){
			int x, y; scanf("%d%d", &x, &y);
			G[x].push_back(y); G[y].push_back(x);
		}
		bfs(ti);
	}
//	LL c0=calc(v[0]), c1=calc(v[1]), c2=calc(v[2]);
//	printf("%lld %lld %lld\n", c0, c1, c2);
	printf("%lld\n", ((calc(v[0])+calc(v[1]))%P-calc(v[2])+P)%P);
	return 0;
}
/*
4

6 9
1 2
6 1
6 5
3 2
4 2
6 3
6 4
2 2
5 5

4 4
1 3
2 1
4 1
4 3

5 5
1 5
1 2
1 4
1 3
3 4

2 2
1 2
2 2

	

*/