#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<map>#include<vector>using namespace std;#define pb push_back#define mp make_pair#define X first#define Y second#define inf 0xffffffftypedef long long lld;#define eps 1e-8#define pi acos(-1.0)#define mod 10000007#define maxn 32bool g[maxn][maxn][maxn];bool flag[maxn][maxn][maxn][maxn];struct Edge{int v,next;}edge[1000010];int head[maxn];int pos;void insert(int x,int y){edge[pos].v=y;edge[pos].next=head[x];head[x]=pos++;}int n,m,src,tc,limit;int dis[maxn][maxn];int queue[maxn];int rear,front;int d[maxn];void judge(int f1,int f2){memset(head,0,sizeof(head));pos=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(flag[f1][f2][i][j])insert(i,j);rear=front=0;queue[front++]=src;for(int i=1;i<=n;i++)d[i]=inf;d[src]=0;while(rear < front){int now=queue[rear++];for(int i=head[now];i;i=edge[i].next){int v=edge[i].v;if(d[v] == inf){d[v]=d[now]+1;queue[front++]=v;}}}dis[f1][f2]=d[tc];}int dp[maxn];int main(){int cas;scanf("%d",&cas);for(int cc=1;cc<=cas;cc++){scanf("%d %d %d %dn",&n,&m,&src,&tc);limit=n;for(int k=1;k<=m;k++){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)g[k][i][j]=false;int T;scanf("%d",&T);while(T--){int x,y;scanf("%d %d",&x,&y);g[k][x][y]=g[k][y][x]=true;}}for(int i=1;i<=m;i++)for(int j=i;j<=m;j++)for(int x=1;x<=n;x++)for(int y=1;y<=n;y++){if(i == j){if(g[i][x][y])flag[i][j][x][y]=true;elseflag[i][j][x][y]=false;}else{if(g[j][x][y] && flag[i][j-1][x][y])flag[i][j][x][y]=true;elseflag[i][j][x][y]=false;}}for(int i=1;i<=m;i++)for(int j=i;j<=m;j++)judge(i,j);for(int i=0;i<=m;i++)dp[i]=inf;for(int i=1;i<=m;i++)if(dis[1][i] != inf)dp[i]=min(dp[i],dis[1][i]*i);for(int i=1;i<m;i++)if(dp[i] != inf)for(int k=i+1;k<=m;k++)if(dis[i+1][k] != inf)dp[k]=min(dp[k],dp[i]+dis[i+1][k]*(k-i)+1);printf("%dn",dp[m]);}return 0;}
